迷路の問題のラット

この問題では、サイズN x Nの迷路があります。送信元と宛先の場所は、それぞれ左上のセルと右下のセルです。一部のセルは移動に有効であり、一部のセルはブロックされています。 1匹のラットが開始頂点から目的頂点に移動し始めた場合、パスを完了する方法があることを見つける必要があります。可能であれば、ラットの正しいパスをマークします。

迷路はバイナリマトリックスを使用して与えられ、1でマークされています。これは有効なパスです。それ以外の場合は、ブロックされたセルの場合は0です。

注： ラットは、右または下の2つの方向にしか移動できません。

入力と出力

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）の場所が有効な場合は真、それ以外の場合は偽。

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

solveRatMaze（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