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

迷宮中的老鼠也是利用回溯的常見問題。 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

範例

#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;
}

#

以上是迷宮中老鼠的C程序 - 回溯法-2的詳細內容。更多資訊請關注PHP中文網其他相關文章！