用 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