資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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查詢解決方案的方法
在這種方法中，我們將使用回溯來跟蹤老鼠可以採取的每條路徑。如果老鼠從任何路徑到達我們的目的地，我們返回該路徑的真值，然後列印該路徑。否則，我們列印該路徑不存在。
示例
#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't exist
//or the path doesn'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't exist\n";
return 0;
}輸出
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
上述程式碼的解釋
在上述方法中，我們檢查老鼠從當前單元格可以進行的每條路徑，並且在檢查時，我們現在將路徑標記為 1。當我們的路徑到達死衚衕時，我們檢查該死衚衕是否是我們的目的地。現在，如果這不是我們的目的地，我們回溯，並且當我們回溯時，我們將單元格標記為 0，因為此路徑無效，這就是我們的程式碼執行的方式。
結論
在本教程中，我們解決了允許多步或跳躍的迷宮中的老鼠問題。我們還學習了此問題的 C++ 程式以及我們用來解決此問題的完整方法（常規）。我們可以用其他語言（如 C、Java、Python 等）編寫相同的程式。我們希望您覺得本教程有幫助。
更新於: 2021 年 11 月 26 日
273 次檢視
廣告