Bolehkah tetikus dalam mez membuat beberapa langkah atau melompat?

Masalah tetikus dalam maze adalah salah satu masalah menjejak ke belakang yang terkenal. Di sini kita akan melihat bahawa masalah kekal hampir tidak berubah. Katakan maze NxN M diberikan. Titik permulaan ialah sudut kiri atas M[0, 0], dan titik akhir ialah sudut kanan bawah M[N – 1, N – 1]. Seekor tetikus diletakkan di titik permulaan. Matlamat kami adalah untuk mencari laluan dari titik permulaan ke titik akhir yang membolehkan tetikus sampai ke destinasinya. Di sini tikus boleh melompat (varian). Kini terdapat beberapa sekatan

• Tetikus boleh bergerak ke kanan atau ke bawah.
• A 0 dalam sel dalam mez bermakna sel itu disekat.
• Sel bukan sifar mewakili laluan yang sah.
• Nombor dalam sel menunjukkan bilangan maksimum lompatan yang boleh dilakukan oleh tikus daripada sel tersebut.
ul>

Algoritma

ratInMaze

begin
   if destination is reached, then
      print the solution matrix
   else
      1. Place the current cell inside the solution matrix as 1
      2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not.
      3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not
      4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0.
   end if
end

Salin selepas log masuk

Contoh

rreee🎜#

#include <iostream>
#define N 4
using namespace std;
void dispSolution(int sol[N][N]) {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << sol[i][j] << " ";
      cout << endl;
   }
}
bool isSafe(int maze[N][N], int x, int y) { //check whether x,y is valid or not
   // when (x, y) is outside of the maze, then return false
   if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
      return true;
   return false;
}
bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {
   if (x == N - 1 && y == N - 1) { //if destination is found, return true
      sol[x][y] = 1;
      return true;
   }
   if (isSafe(maze, x, y)) {
      sol[x][y] = 1; //mark 1 into solution matrix
      for (int i = 1; i <= maze[x][y] && i < N; i++) {
         if (ratMazeSolve(maze, x + i, y, sol)) //move right
            return true;
         if (ratMazeSolve(maze, x, y + i, sol)) //move down
            return true;
      }
      sol[x][y] = 0; //if the solution is not valid, then make it 0
      return false;
   }
   return false;
}
bool solveMaze(int maze[N][N]) {
   int sol[N][N] = { { 0, 0, 0, 0 },
      { 0, 0, 0, 0 },
      { 0, 0, 0, 0 },
      { 0, 0, 0, 0 }
   };
   if (!ratMazeSolve(maze, 0, 0, sol)) {
      cout << "Solution doesn&#39;t exist";
      return false;
   }
   dispSolution(sol);
   return true;
}
main() {
   int maze[N][N] = { { 2, 1, 0, 0 },
      { 3, 0, 0, 1 },
      { 0, 1, 0, 1 },
      { 0, 0, 0, 1 }
   };
   solveMaze(maze);
}

Salin selepas log masuk
#🎜#

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

Salin selepas log masuk
#🎜 🎜 🎜 #

Atas ialah kandungan terperinci Bolehkah tetikus dalam mez membuat beberapa langkah atau melompat?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!