迷宫中的老鼠

在此问题中，有一个给定的大小为N x N的迷宫。源位置和目标位置分别是左上角的单元格和右下角的单元格。一些单元格可以移动，而某些单元格被阻止。如果一只老鼠开始从起始顶点移动到目标顶点，我们必须找到可以完成该路径的任何方法，如果可能的话，请为该老鼠标记正确的路径。

迷宫使用二进制矩阵给出，其中用1标记，这是有效路径，否则为0表示被阻塞的单元格。

注意： 老鼠只能在两个方向上移动，即向右或向下移动。

输入输出

Input:
This algorithm will take the maze as a matrix.
In the matrix, the value 1 indicates the free space and 0 indicates the wall or blocked area.In this diagram, the top-left circle indicates the starting point and the bottom-right circle indicates the ending point.
Output:
It will display a matrix. From that matrix, we can find the path of the rat to reach the destination point.

算法

isValid(x,y)

输入： x和y点在迷宫中。

输出： 如果(x,y)位置有效，则为true，否则为false。

Begin
   if x and y are in range and (x,y) place is not blocked, then
      return true
   return false
End

resolveRatMaze(x,y)

输入-起点x和y。

输出 -老鼠到达目的地所遵循的路径，否则为false。

Begin
   if (x,y) is the bottom right corner, then
      mark the place as 1
      return true
   if isValidPlace(x, y) = true, then
      mark (x, y) place as 1
      if solveRatMaze(x+1, y) = true, then //for forward movement
         return true
      if solveRatMaze(x, y+1) = true, then //for down movement
         return true
      mark (x,y) as 0 when backtracks
      return false
   return false
End

示例

#include<iostream>
#define N 5
using namespace std;

int maze[N][N]  =  {
   {1, 0, 0, 0, 0},
   {1, 1, 0, 1, 0},
   {0, 1, 1, 1, 0},
   {0, 0, 0, 1, 0},
   {1, 1, 1, 1, 1}
};

int sol[N][N];         //final solution of the maze path is stored here
void showPath() {
   for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++)
         cout << sol[i][j] << " ";
      cout << endl;
   }
}

bool isValidPlace(int x, int y) {      //function to check place is inside the maze and have value 1
   if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
      return true;
   return false;
}

bool solveRatMaze(int x, int y) {
   if(x == N-1 && y == N-1) {       //when (x,y) is the bottom right room
      sol[x][y] = 1;
      return true;
   }

   if(isValidPlace(x, y) == true) {     //check whether (x,y) is valid or not
      sol[x][y] = 1; //set 1, when it is valid place
      if (solveRatMaze(x+1, y) == true)       //find path by moving right direction
         return true;
      if (solveRatMaze(x, y+1) == true)         //when x direction is blocked, go for bottom direction
         return true;
      sol[x][y] = 0;         //if both are closed, there is no path
      return false;
   }  
   return false;
}

bool findSolution() {
   if(solveRatMaze(0, 0) == false) {
      cout << "There is no path";
      return false;
   }
   showPath();
   return true;
}

int main() {
   findSolution();
}

输出结果

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