C++ 允許多步或跳躍的迷宮中的老鼠

給定一個 n*n 網格迷宮。我們的老鼠出現在網格的左上角。現在，老鼠只能向下或向前移動，並且當且僅當該塊現在具有非零值時，在此變體中，老鼠才可以進行多次跳躍。老鼠從當前單元格中可以進行的最大跳躍是單元格中存在的數字，現在您的任務是找出老鼠是否可以到達網格的右下角，例如-

Input : { { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
},
Output : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}

Input : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
Output: Path doesn't exist

尋找解決方案的方法

在這種方法中，我們將使用回溯來追蹤老鼠現在可以採取的每條路徑。如果老鼠從任何路徑到達目的地，我們都會對該路徑返回 true，然後列印該路徑。否則，我們列印該路徑不存在。

範例

 
#include <bits/stdc++.h>
using namespace std;
#define N 4 // size of our grid
bool solveMaze(int maze[N][N], int x, int y, // recursive function for finding the path
    int sol[N][N]){
        if (x == N - 1 && y == N - 1) { // if we reached our goal we return true and mark our goal as 1
            sol[x][y] = 1;
            return true;
    }
    if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
        sol[x][y] = 1; // we include this index as a path
        for (int i = 1; i <= maze[x][y] && i < N; i++) { // as maze[x][y] denotes the number of jumps you can take                                             //so we check for every jump in every direction
            if (solveMaze(maze, x + i, y, sol) == true) // jumping right
               return true;
            if (solveMaze(maze, x, y + i, sol) == true) // jumping downward
               return true;
        }
        sol[x][y] = 0; // if none are true then the path doesn&#39;t exist
                   //or the path doesn&#39;t contain current cell in it
        return false;
    }
    return false;
}
int main(){
    int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 },
                   { 0, 0, 0, 1 } };
    int sol[N][N];
    memset(sol, 0, sizeof(sol));
    if(solveMaze(maze, 0, 0, sol)){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++)
                cout << sol[i][j] << " ";
            cout << "\n";
        }
    }
    else
        cout << "Path doesn&#39;t exist\n";
    return 0;
}

輸出

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1

上述程式碼的說明

在上述方法中，我們檢查它可以從目前儲存格產生的每個路徑，在檢查時，我們現在將路徑標記為一條。當我們的路徑到達死胡同時，我們檢查該死胡同是否是我們的目的地。現在，如果那不是我們的目的地，我們就回溯，當我們回溯時，我們將單元格標記為 0，因為該路徑無效，這就是我們的程式碼的處理方式。

結論

在本教程中，我們將解決迷宮中的老鼠問題，允許多個步驟或跳躍。我們也學習了該問題的 C 程序以及解決該問題的完整方法（普通）。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。我們希望本教學對您有所幫助。

以上是C++ 允許多步或跳躍的迷宮中的老鼠的詳細內容。更多資訊請關注PHP中文網其他相關文章！