迷宮中的老鼠也是利用回溯的常見問題。 I
迷宮是一個二維矩陣，其中一些細胞被阻擋。其中一個單元格是來源單元格，我們必須從這裡開始。其中另一個是目的地，我們必須到達的地方。我們必須找到一條從來源到目的地的路徑，而不需要進入任何被封鎖的儲存格。下面顯示了未解決的迷宮的圖片。
這就是它的解決方案。
為了解決這個難題，我們先從源單元開始，朝路徑不被阻擋的方向移動。如果所採取的路徑使我們到達目的地，那麼難題就解決了。否則，我們會回來改變我們所走的道路的方向。我們也將在程式碼中實現相同的邏輯。
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
現在，我們將再製作一個相同維度的矩陣來儲存解。它的元素也將為 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
因此，我們現在有了我們的矩陣。接下來，我們將找到從起始單元格到目標單元格的路徑，我們將採取的步驟如下：
#檢查當前單元格，如果它是目標單元格，則拼圖已解決。
如果不是，請嘗試向下移動並查看是否可以移動到下一個單元格（要移動到一個單元格，它必須是空的且不在路徑中）。
如果可以移動到下一個儲存格，則繼續沿著路徑移動到下一個下方儲存格。
如果不能，則嘗試向右移動。如果右側被阻塞或已佔用，則向上移動。
同樣，如果向上移動不可能，我們將簡單地移動到左側單元格。
如果四個方向（向下，向右，向上或向左）都無法移動，則簡單地返回並更改當前路徑（回溯）。
因此，總結一下，我們嘗試從當前單元格移動到其他單元格（向下，向右，向上和向左），如果沒有移動可能，則返回並將路徑的方向變更為另一個儲存格。
printsolution → 此函數只是列印解決方案矩陣。
solvemaze → 這是實際實作回溯演算法的函數。首先，我們檢查我們的儲存格是否是目標儲存格，如果是（r==SIZE-1）和（c==SIZE-1）。如果是目標單元格，則我們的拼圖已經解決。如果不是，則我們檢查它是否是一個有效的移動單元格。有效的單元格必須在矩陣中，即索引必須在0到SIZE-1之間，r>=0 && c>=0 && r 以上是迷宮中老鼠的C程序 - 回溯法-2的詳細內容。更多資訊請關注PHP中文網其他相關文章！範例
#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("</p><p></p><p>");
}
}
//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</p><p>");
return 0;
}
