Program C untuk tikus dalam maze - backtracking-2

Tikus dalam labirin juga merupakan masalah biasa menggunakan pengunduran. I

Maze ialah matriks dua dimensi di mana beberapa sel disekat. Salah satu sel ialah sel sumber dan kita perlu bermula dari situ. Satu lagi ialah destinasi, tempat yang mesti kita sampai. Kita perlu mencari laluan dari sumber ke destinasi tanpa memasuki mana-mana sel yang disekat. Gambar maze yang belum diselesaikan ditunjukkan di bawah.

Ini adalah penyelesaian untuknya.

Untuk menyelesaikan teka-teki ini, kita mula-mula bermula dari unit sumber dan bergerak ke arah di mana laluan tidak disekat. Jika jalan yang dilalui membawa kita ke destinasi kita, teka-teki telah diselesaikan. Jika tidak, kita akan kembali dan mengubah arah jalan yang kita lalui. Kami akan melaksanakan logik yang sama dalam kod juga.

Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}

Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

Penjelasan

Pertama, kita akan buat matriks untuk mewakili maze, elemen matriks akan menjadi 0 atau 1. 1 bermaksud sel tersumbat dan 0 bermaksud sel yang boleh kita gerakkan. Matriks untuk maze yang ditunjukkan di atas adalah seperti berikut:

0 1 0 1 1
0 0 0 0 0
1 0 1 0 1
0 0 1 0 0
1 0 0 1 0

Sekarang, kami akan membuat satu lagi matriks dengan dimensi yang sama untuk menyimpan penyelesaian. Elemennya juga akan menjadi 0 atau 1. 1 akan mewakili sel dalam laluan kita dan sel yang tinggal ialah 0. Matriks yang mewakili penyelesaian ialah:

1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

Jadi, kami kini mempunyai matriks kami. Seterusnya, kita akan mencari laluan dari sel permulaan ke sel sasaran, langkah yang akan kita ambil adalah seperti berikut:

• Semak sel semasa, jika ia adalah sel sasaran, teka-teki diselesaikan.

• Jika tidak, cuba bergerak ke bawah dan lihat jika anda boleh bergerak ke sel seterusnya (untuk berpindah ke sel, ia mesti kosong dan tidak berada di laluan).

• Jika anda boleh berpindah ke sel seterusnya, teruskan bergerak di sepanjang laluan ke sel bawah seterusnya.

• Jika tidak, cuba bergerak ke kanan. Jika bahagian kanan disekat atau diduduki, bergerak ke atas.

• Begitu juga, jika bergerak ke atas tidak boleh, kita hanya akan bergerak ke sel kiri.

• Jika pergerakan tidak boleh dilakukan dalam mana-mana daripada empat arah (bawah, kanan, atas atau kiri), hanya berundur dan tukar laluan semasa (backtracking).

Jadi, untuk meringkaskan, kami cuba beralih dari sel semasa ke sel lain (bawah, kanan, atas dan kiri) dan jika tiada pergerakan boleh, kembali dan tukar arah laluan ke grid sel yang lain.

printsolution → Fungsi ini hanya mencetak matriks penyelesaian.

solvemaze → Ini ialah fungsi yang sebenarnya melaksanakan algoritma penjejakan ke belakang. Mula-mula, kita semak sama ada sel kita ialah sel sasaran, jika ya (r==SAIZ-1) dan (c==SAIZ-1). Jika ia adalah sel sasaran, teka-teki kami telah diselesaikan. Jika tidak, maka kami menyemak sama ada ia adalah sel mudah alih yang sah. Sel yang sah mesti berada dalam matriks, iaitu indeks mestilah antara 0 dan SIZE-1, r>=0 && c>=0 && r

Contoh

#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
   {0,1,0,1,1},
   {0,0,0,0,0},
   {1,0,1,0,1},
   {0,0,1,0,0},
   {1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
   int i,j;
   for(i=0;i<SIZE;i++) {
      for(j=0;j<SIZE;j++) {
         printf("%d\t",solution[i][j]);
      }
      printf("</p><p></p><p>");
   }
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
   //if destination is reached, maze is solved
   //destination is the last cell(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1) {
      solution[r][c] = 1;
      return 1;
   }
   //checking if we can visit in this cell or not
   //the indices of the cell must be in (0,SIZE-1)
   //and solution[r][c] == 0 is making sure that the cell is not already visited
   //maze[r][c] == 0 is making sure that the cell is not blocked
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      //if safe to visit then visit the cell
      solution[r][c] = 1;
      //going down
      if(solvemaze(r+1, c))
         return 1;
      //going right
      if(solvemaze(r, c+1))
         return 1;
      //going up
      if(solvemaze(r-1, c))
         return 1;
      //going left
      if(solvemaze(r, c-1))
         return 1;
      //backtracking
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   //making all elements of the solution matrix 0
   int i,j;
   for(i=0; i<SIZE; i++) {
      for(j=0; j<SIZE; j++) {
         solution[i][j] = 0;
      }
   }
   if (solvemaze(0,0))
      printsolution();
   else
      printf("No solution</p><p>");
   return 0;
}

Atas ialah kandungan terperinci Program C untuk tikus dalam maze - backtracking-2. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!