是一个简易迷宫找出口的问题
这是出现的问题,试过加头文件,改成emplace,都不行
#include<iostream>
#include<vector>
#undef UNICODE
#undef _UNICODE
using namespace std;
int maze[4][6] = { {1,1,0,0,0,0},
{0,1,1,1,0,0},
{1,1,0,1,0,0},
{0,0,0,1,0,0} };
vector<pair<int, int>>path;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
void search(vector<pair<int, int>>tpath,int x,int y)
{
if (x < 0 || y < 0 || x>5 || y>3)
return;
if (x == 3 && y == 3)
{
path = tpath;
return;
}
for (int ix = 0; ix < 4; ix++)
{
if (maze[x + dir[ix][0]][y + dir[ix][1]] == 1)
{
tpath.push_back(make_pair<x, y>);
search(tpath, x + dir[ix][0], y + dir[ix][1]);
tpath.pop_back();
}
}
}
int main()
{
vector<pair<int, int>>tpath;
search(tpath, 0, 0);
return 0;
}
看起来你的代码中有一些小错误。这是我对你代码的修正:
#include<iostream>
#include<vector>
using namespace std;
int maze[4][6] = { {1,1,0,0,0,0},
{0,1,1,1,0,0},
{0,0,0,1,1,1},
{0,0,0,0,0,1} };
vector<pair<int, int>>path;
int dir[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
void search(vector<pair<int, int>>& tpath, int x, int y)
{
if (x < 0 || y < 0 || x > 3 || y > 5 || maze[x][y] == 0)
return;
if (x == 3 && y == 5)
{
path = tpath;
path.push_back({x, y});
return;
}
tpath.push_back({x, y});
maze[x][y] = 0; // mark as visited
for (int i = 0; i < 4; i++)
{
int nx = x + dir[i][0];
int ny = y + dir[i][1];
search(tpath, nx, ny);
}
maze[x][y] = 1; // unmark as visited
tpath.pop_back();
}
int main()
{
vector<pair<int, int>>tpath;
search(tpath, 0, 0);
// print the path
for (auto p : path) {
cout << "(" << p.first << "," << p.second << ")" << endl;
}
return 0;
}
这个程序使用了深度优先搜索(DFS)的方法来寻找迷宫的出口。注意在进入每一个位置后,我们需要标记为已访问(这里通过将 maze[x][y]
设为 0 实现),避免重复访问。然后在每次返回时,我们需要将标记取消(设为 1),这样才能在其他路径中重新访问这个位置。
另外,我将迷宫的出口修改为 (3,5)
,因为你的 maze
数组是一个 4x6
的数组,所以 x
的范围应该是 0-3
,y
的范围应该是 0-5
。根据你的原始代码,你将 x
和 y
的范围分别设置为 0-5
和 0-3
,这可能会导致访问越界。
我也在 main
函数中添加了打印路径的代码,这样你可以看到找到的路径。