在C ++中找到迷宫中从角单元到中间单元的路径
假设我们有一个充满数字的方形迷宫；我们必须找到从角单元到中间单元的所有路径。在这里，我们将从一个单元格沿向上，向下，向右和向左四个方向精确执行n个步骤，其中n是该单元格的值。因此，我们可以从单元格[i，j]中将单元格[i+n，j]移至[in，j]，[i，j+n]和[i，jn]，其中n是单元格[i，j]。
所以，如果输入像
那么输出将是
(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时返回true
定义一个数组dir_row：={-1，1，0，0}
定义一个数组dir_col：={0，0，-1，1，1}
定义一个数组行：={0，0，N-1，N-1}
定义一个数组col：={0，N-1，0，N-1}
定义一个函数solve()，它将使用迷宫，路径，一组访问的对，一对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（已访问，下一个），则-
从主要方法中，执行以下操作-
定义一组称为访问的对
对于初始化i：=0，当i<4时，更新（将i增加1），请执行-
x：=行[i]
y：=col[i]
pt：=使用(x,y)配对
将pt插入访问过的
在路径末尾插入pt
解决（迷宫，路径，已访问，pt）
从路径中删除最后一个元素
从访问中删除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