資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究迷宮中的老鼠可以跳躍或進行多步走動？
迷宮中的老鼠問題是回溯演算法中一個非常著名的難題。我們在這裡將看到這一難題的變種。假設有一個NxN的迷宮M，起點是左上角M[0, 0]，終點是右下角M[N – 1, N - 1]。將一個老鼠放置在起點。我們的目的是找到一條從起點到終點的道路，這樣老鼠就可以到達終點。老鼠現在可以跳躍（變數）。現在有一些約束：
- 老鼠可以向右或向下移動。
- 迷宮中單元格中的0表示該單元格被阻塞。
- 非零單元格表示有效的路徑。
- 單元格中的數字表示老鼠從該單元格可以進行的最大跳躍數。
演算法
ratInMaze
begin if destination is reached, then print the solution matrix else 1. Place the current cell inside the solution matrix as 1 2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not. 3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not 4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0. end if end
示例
#include <iostream>
#define N 4
using namespace std;
void dispSolution(int sol[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << endl;
}
}
bool isSafe(int maze[N][N], int x, int y) { //check whether x,y is valid or not
// when (x, y) is outside of the maze, then return false
if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
return true;
return false;
}
bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {
if (x == N - 1 && y == N - 1) { //if destination is found, return true
sol[x][y] = 1;
return true;
}
if (isSafe(maze, x, y)) {
sol[x][y] = 1; //mark 1 into solution matrix
for (int i = 1; i <= maze[x][y] && i < N; i++) {
if (ratMazeSolve(maze, x + i, y, sol)) //move right
return true;
if (ratMazeSolve(maze, x, y + i, sol)) //move down
return true;
}
sol[x][y] = 0; //if the solution is not valid, then make it 0
return false;
}
return false;
}
bool solveMaze(int maze[N][N]) {
int sol[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 }
};
if (!ratMazeSolve(maze, 0, 0, sol)) {
cout << "Solution doesn't exist";
return false;
}
dispSolution(sol);
return true;
}
main() {
int maze[N][N] = { { 2, 1, 0, 0 },
{ 3, 0, 0, 1 },
{ 0, 1, 0, 1 },
{ 0, 0, 0, 1 }
};
solveMaze(maze);
}輸出
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
更新時間：2019年7月31日
368 次瀏覽
廣告