迷路の中のラットのためのCプログラム-バックトラッキング-2？

迷路の中のネズミも、バックトラックを利用する一般的な問題の1つです。私

迷路は、一部のセルがブロックされている2Dマトリックスです。セルの1つはソースセルであり、そこから開始する必要があります。そしてもう1つは、私たちが到達しなければならない目的地です。ブロックされたセルに移動せずに、送信元から宛先までのパスを見つける必要があります。未解決の迷路の写真を以下に示します。

そしてこれがその解決策です。

このパズルを解くために、最初にソースセルから始めて、パスがブロックされていない方向に移動します。道をたどると目的地にたどり着くことができれば、パズルは解かれます。そうでなければ、私たちは戻ってきて、たどった道の方向を変えます。コードにも同じロジックを実装します。

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

説明

まず、迷路を表す行列を作成します。行列の要素は0または1になります。1はブロックされたセルを表し、0は移動できるセルを表します。上に示した迷路のマトリックスは次のとおりです。

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

次に、ソリューションを格納するために、同じ次元の行列をもう1つ作成します。その要素も0または1になります。1はパス内のセルを表し、残りのセルは0になります。ソリューションを表す行列は次のとおりです。

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

これで、行列ができました。次に、ソースセルから宛先セルへのパスを見つけます。実行する手順は次のとおりです。

• 現在のセルを確認します。宛先セルの場合、パズルは解かれます。

• そうでない場合は、下に移動して、下のセルに移動できるかどうかを確認します（セルに移動するには、セルが空で、パスにまだ存在していない必要があります）。

• そこに移動できれば、次の下向きのセルへのパスを続行します。

• そうでない場合は、右側のセルに移動しようとします。そして、それがブロックされたり、奪われたりした場合は、上に移動します。

• 同様に、上に移動できない場合は、単に左のセルに移動します。

• 4つの移動（下、右、上、または左）のいずれも不可能な場合は、単に戻って現在のパスを変更します（バックトラック）。

したがって、要約すると、現在のセルから他のセル（下、右、上、左）に移動しようとします。移動できない場合は、戻って別のセルへのパスの方向を変更します。

printsolution→この関数は、ソリューションマトリックスを印刷するだけです。

Solvemaze→これは、バックトラッキングアルゴリズムを実装している実際の関数です。まず、（r ==SIZE-1）および（c ==SIZE-1）の場合、セルが宛先セルであるかどうかを確認します。それが宛先セルである場合、私たちのパズルはすでに解決されています。そうでない場合は、移動するのが有効なセルであるかどうかを確認しています。有効なセルはマトリックス内にある必要があります。つまり、インデックスは0からSIZE-1の間でなければなりません。r> =0 &&c> =0 &&r

例

#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("\n\n");
   }
}
//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\n");
   return 0;
}