資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究用 C++ 查詢迷宮中角單元格到中間單元格的所有路徑
假設我們有一個充滿數字的方形迷宮；我們必須找到從角單元格到中間單元格的所有路徑。在這裡，我們將從一個單元格出發，沿著四個方向（上、下、左、右）精確移動 n 步，其中 n 是該單元格的值。因此，我們可以從單元格 [i,j] 移動到單元格 [i+n,j]、[i-n, j]、[i, j+n] 和 [i, j-n]，其中 n 是單元格 [i, j] 的值。
所以，如果輸入像這樣
| 3 | 4 | 4 | 4 | 7 | 3 | 4 | 6 | 3 |
| 6 | 7 | 5 | 6 | 6 | 2 | 6 | 6 | 2 |
| 3 | 3 | 4 | 3 | 2 | 5 | 4 | 7 | 2 |
| 6 | 5 | 5 | 1 | 2 | 3 | 6 | 5 | 6 |
| 3 | 3 | 4 | 3 | 0 | 1 | 4 | 3 | 4 |
| 3 | 3 | 4 | 3 | 2 | 1 | 3 | 3 | 5 |
| 3 | 5 | 4 | 3 | 2 | 6 | 4 | 4 | 3 |
| 3 | 5 | 1 | 3 | 7 | 5 | 3 | 6 | 3 |
| 6 | 2 | 4 | 3 | 4 | 5 | 4 | 5 | 1 |
那麼輸出將是
(0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1)→(4, 4)→中間
(0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→中間
(0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→中間
(0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→中間
(8, 8)→(7, 8)→(4, 8)→(4, 4)→中間
為了解決這個問題，我們將遵循以下步驟：
N := 9
定義一個函式 is_ok()，它將接收一個稱為 visited 的對集和一個對 pt，
當 pt 的第一和第二元素在 0 到 N 的範圍內且 pt 不在 visited 中時返回 true
定義一個數組 dir_row := { - 1, 1, 0, 0}
定義一個數組 dir_col := { 0, 0, - 1, 1}
定義一個數組 row := { 0, 0, N - 1, N - 1}
定義一個數組 col := { 0, N - 1, 0, N - 1}
定義一個函式 solve()，它將接收迷宮 maze、路徑 path、一個稱為 visited 的對集和一個對 curr，
如果 curr 的第一和第二個元素與 N / 2 相同，則：
顯示路徑
返回
初始化 i := 0，當 i < 4 時，更新（i 增加 1），執行：
n := maze[curr.first, curr.second]
x := curr.first + dir_row[i] * n
y := curr.second + dir_col[i] * n
n := 使用 x、y 建立的一個對
如果 is_ok(visited, next) 為真，則：
將 next 插入 visited
將 next 插入 path 的末尾
solve(maze, path, visited, next)
從 path 中刪除最後一個元素
從 visited 中刪除 next
從 main 方法中執行以下操作：
定義一個稱為 visited 的對集
初始化 i := 0，當 i < 4 時，更新（i 增加 1），執行：
x := row[i]
y := col[i]
pt := 使用 (x, y) 建立一個對
將 pt 插入 visited
將 pt 插入 path 的末尾
solve(maze, path, visited, pt)
從 path 中刪除最後一個元素
從 visited 中刪除 pt
示例（C++）
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
for (auto it = path.begin(); it != path.end(); it++)
cout << "(" << it->first << ", " << it->second << ")->";
cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
if (curr.first == N / 2 && curr.second == N / 2) {
display_path(path);
return;
}
for (int i = 0; i < 4; ++i) {
int n = maze[curr.first][curr.second];
int x = curr.first + dir_row[i]*n;
int y = curr.second + dir_col[i]*n;
pair<int, int> next = make_pair(x, y);
if (is_ok(visited, next)) {
visited.insert(next);
path.push_back(next);
solve(maze, path, visited, next);
path.pop_back();
visited.erase(next);
}
}
}
void search_path(int maze[N][N]) {
list<pair<int, int> > path;
set<pair<int, int> > visited;
for (int i = 0; i < 4; ++i) {
int x = row[i];
int y = col[i];
pair<int, int> pt = make_pair(x, y);
visited.insert(pt);
path.push_back(pt);
solve(maze, path, visited, pt);
path.pop_back();
visited.erase(pt);
}
}
int main() {
int maze[N][N] = {
{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}
};
search_path(maze);
}輸入
{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}}輸出
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE
242 次檢視
