迷宫中的老鼠
在此问题中，有一个给定的大小为NxN的迷宫。源位置和目标位置分别是左上角的单元格和右下角的单元格。一些单元格可以移动，而某些单元格被阻止。如果一只老鼠开始从起始顶点移动到目标顶点，我们必须找到可以完成该路径的任何方法，如果可能的话，请为该老鼠标记正确的路径。
迷宫使用二进制矩阵给出，其中用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
EndresolveRatMaze(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