迷路内のマウスのための C プログラム - バックトラッキング-2-C++-php.cn

迷路内のマウスのための C プログラム - バックトラッキング-2

WBOY

リリース： 2023-09-11 14:25:21

転載

508 人が閲覧しました

迷路の中のネズミも、バックトラッキングを使用する一般的な問題です。 I

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

迷宫中老鼠的C程序 - 回溯法-2

#これが解決策です。

迷宫中老鼠的C程序 - 回溯法-2

このパズルを解くには、まずソースユニットから開始して、経路がブロックされていない方向に移動します。たどった道が目的地につながっていれば、パズルは解けます。そうでないと、戻ってきて、今いる道の方向を変えることになります。同じロジックをコードにも実装します。

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 になります。1 はパス内のセルを表し、残りのセルは 0 になります。解を表す行列は次のとおりです。

ログイン後にコピー

これで、行列が完成しました。次に、開始セルからターゲットセルまでのパスを見つけます。実行する手順は次のとおりです。

現在のセルを確認し、それがターゲットセルである場合は、パズルは解けました。
そうでない場合は、下に移動して、次のセルに移動できるかどうかを確認してください (セルに移動するには、セルが空であり、パス内にない必要があります)。
次のセルに移動できる場合は、パスに沿って次の下のセルまで移動を続けます。

printsolution → この関数は単純に解行列を出力します。

solvemaze → これはバックトラッキングアルゴリズムを実際に実装する関数です。まず、セルがターゲットセルであるかどうかを確認します。ターゲットセルである場合は (r==SIZE-1) および (c==SIZE-1) となります。それがターゲットのセルであれば、パズルは解けたことになります。そうでない場合は、それが有効なモバイルセルであるかどうかを確認します。有効なセルが行列内に存在する必要があります。つまり、インデックスは 0 から SIZE-1 の間でなければならず、r>=0 && c>=0 && r

例

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

ログイン後にコピー

以上が迷路内のマウスのための C プログラム - バックトラッキング-2の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。