使用 BFS 输出错误的迷宫路线
Wrong Maze Route output using BFS
我正在创建一个程序，它将找到穿过迷宫的最短路径并将该路径输出为字符串。我已经利用 BFS 找到了最短的移动，现在我需要输出这些移动是什么。在我的代码中，我尝试使用 switch 语句向字符串添加字符，因为它解决了迷宫问题。它利用了 for 循环中的值，但没有成功。我还尝试创建 2 个不同的开关，一个检查行 int，一个检查 col int。然而，这也没有成功。
我可以解决一些迷宫，例如：
xxxxx
x...B
A...x
xxxxx
这正确输出：
Shortest route is: ENEEE
Shortest Path is 5
然而，我要解决的另一个迷宫是：
xxxxxxxxxx
x........x
x..xxxx..x
x..xxxx..x
A..xxxx..B
x..xxxx..x
x........x
x........x
xxxxxxxxxx
这导致输出：
Shortest route is: ENESNESSNESSE
Shortest Path is 13
虽然距离正确，但路线本身不正确。如果有人能发现我遗漏的东西，请告诉我。
请在下面找到我的代码：
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
struct Point
{
int x;
int y;
};
struct queueNode
{
Point pt;
int dist;
};
bool isValid(int row, int col, int x, int y)
{
return (row >= 0) && (row < x) && (col >= 0) && (col < y);
}
bool isSafe(vector<vector<char>> maze, vector<vector<int>> visited, int x, int y)
{
if (maze[x][y] == 'x' || visited[x][y] || maze[x][y] == NULL)
return false;
else
return true;
}
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
int solveMaze(vector<vector<char>> maze, Point src, Point dest, int rows, int columns)
{
string route;
if (!maze[src.x][src.y] || !maze[dest.x][dest.y])
return -1;
auto visited = vector<vector<int>>(rows, vector<int>(columns));
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for solveMaze
queue<queueNode> q;
// Distance of source cell is 0
queueNode s = { src, 0 };
q.push(s); // Enqueue source cell
// Do a solveMaze starting from source cell
while (!q.empty())
{
queueNode curr = q.front();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
{
route.resize(curr.dist);
cout << "Shortest route is: " << route << endl;
return curr.dist;
}
// Otherwise dequeue the front
// cell in the queue
// and enqueue its adjacent cells
q.pop();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path and
// not visited yet, enqueue it.
if (isValid(row, col, rows, columns) && maze[row][col] && !visited[row][col] && isSafe(maze,visited,row,col))
{
switch (i)
{
case 0:
route.append("N");
break;
case 1:
route.append("W");
break;
case 2:
route.append("E");
break;
case 3:
route.append("S");
break;
}
visited[row][col] = true;
queueNode Adjcell = { {row, col},curr.dist + 1 };
q.push(Adjcell);
}
}
}
return -1;
}
int main()
{
string filename;
int rows;
int columns;
cout << "Please input the name of your maze!" << endl;
cin >> filename;
cout << endl;
cout << "Please input the amount of rows in your maze!" << endl;
cin >> rows;
cout << endl;
cout << "Please input the amount of columns in your maze!" << endl;
cin >> columns;
cout << endl;
int startRow = 0;
int startColumn = 0;
int endRow = 0;
int endColumn = 0;
int column = 0;
auto maze = vector<vector<char>>(rows,vector<char>(columns));
ifstream input(filename);
char data = input.get();
while (!input.eof())
{
for (int row = 0; row < rows; row++)
{
while (data != '\n' && !input.eof())
{
if (data == 'A')
{
startRow = row;
startColumn = column;
}
if (data == 'B')
{
endRow = row;
endColumn = column;
}
maze[row][column] = data;
column++;
data = input.get();
}
column = 0;
data = input.get();
}
}
input.close();
cout << "The Maze being solved is: " << endl;
for (int y = 0; y < rows; y++)
{
for (int x = 0; x < columns; x++)
{
cout << maze[y][x];
}
cout << endl;
}
Point source = { startRow, startColumn };
Point dest = { endRow, endColumn };
int dist = solveMaze(maze, source, dest,rows,columns);
if (dist != -1)
cout << "Shortest Path is " << dist;
else
cout << "Shortest Path doesn't exist";
return 0;
}
在我看来，您在 BFS 期间向路由附加了一个字符。这不会 return 正确的最短路径，因为代码需要验证哪个方向实际对应于最短路径。通过在实际测试路径是否是 最短 路径的一部分之前向路径添加方向，输出实际上只是告诉我们 BFS 本身的执行路径。
为了解决这个问题，我们使用了一个父数组，它保留了每个节点的父节点（当您第一次访问相邻单元格时，将该单元格的父节点设置为当前单元格）。广度优先搜索完成后，将“tracer”变量设置为目标，并使用父数组向后跟踪，直到到达起点。请注意，最后的这个“路径重建”以逆序重建路径（因为我们从目的地迭代回到起点）。
这是我实现这种方法的代码：
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
void bfs(vector <vector<char>> &grid, int R, int C, int sR, int sC, int eR, int eC){
vector <vector<bool>> visited(R, vector <bool> (C, false));
map <pair<int, int>, pair <int, int>> parent;
queue <pair<int, int>> Q;
Q.push({sR, sC});
visited[sR][sC] = true;
parent[{sR, sC}] = {sR, sC}; // it doesn't really matter what you set it to
while(!Q.empty()){
int r = Q.front().first, c = Q.front().second;
Q.pop();
if(r == eR && c == eC){
break;
}
// enqueue all "valid" (unvisited, not-a-wall) adjacent squares
if(r > 0 && !visited[r-1][c] && grid[r-1][c] != 'x'){
visited[r-1][c] = true;
parent[{r-1, c}] = {r, c};
Q.push({r-1, c});
}
if(r < R-1 && !visited[r+1][c] && grid[r+1][c] != 'x'){
visited[r+1][c] = true;
parent[{r+1, c}] = {r, c};
Q.push({r+1, c});
}
if(c > 0 && !visited[r][c-1] && grid[r][c-1] != 'x'){
visited[r][c-1] = true;
parent[{r, c-1}] = {r, c};
Q.push({r, c-1});
}
if(c < C-1 && !visited[r][c+1] && grid[r][c+1] != 'x'){
visited[r][c+1] = true;
parent[{r, c+1}] = {r, c};
Q.push({r, c+1});
}
}
if(visited[eR][eC] == false){
cout << "The destination was unreachable from the source." << endl;
return;
}
// trace back from the destination to the start
pair <int, int> tracer = {eR, eC};
vector <char> path;
// note that this loop constructs the path in reverse order because
// we iterate from the end back to the start
while(tracer != make_pair(sR, sC)){
pair <int, int> next = parent[tracer];
if(next.first - tracer.first == 1){
path.push_back('N');
}
else if(next.first - tracer.first == -1){
path.push_back('S');
}
else if(next.second - tracer.second == 1){
path.push_back('L');
}
else if(next.second - tracer.second == -1){
path.push_back('R');
}
tracer = next;
}
cout << "Shortest Path Length: " << path.size() << endl;
// we print this in reverse order (see the above comment)
for(int i = path.size()-1; i >= 0; --i){
cout << path[i];
}
cout << endl;
}
int main()
{
int R, C, sR, sC, eR, eC;
cin >> R >> C;
vector <vector<char>> grid(R, vector <char> (C));
for(int i = 0; i < R; ++i){
for(int j = 0; j < C; ++j){
cin >> grid[i][j];
if(grid[i][j] == 'A'){
sR = i;
sC = j;
}
else if(grid[i][j] == 'B'){
eR = i;
eC = j;
}
}
}
// Input Done
bfs(grid, R, C, sR, sC, eR, eC);
return 0;
}
我正在创建一个程序，它将找到穿过迷宫的最短路径并将该路径输出为字符串。我已经利用 BFS 找到了最短的移动，现在我需要输出这些移动是什么。在我的代码中，我尝试使用 switch 语句向字符串添加字符，因为它解决了迷宫问题。它利用了 for 循环中的值，但没有成功。我还尝试创建 2 个不同的开关，一个检查行 int，一个检查 col int。然而，这也没有成功。
我可以解决一些迷宫，例如：
xxxxx
x...B
A...x
xxxxx
这正确输出：
Shortest route is: ENEEE
Shortest Path is 5
然而，我要解决的另一个迷宫是：
xxxxxxxxxx
x........x
x..xxxx..x
x..xxxx..x
A..xxxx..B
x..xxxx..x
x........x
x........x
xxxxxxxxxx
这导致输出：
Shortest route is: ENESNESSNESSE
Shortest Path is 13
虽然距离正确，但路线本身不正确。如果有人能发现我遗漏的东西，请告诉我。
请在下面找到我的代码：
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
struct Point
{
int x;
int y;
};
struct queueNode
{
Point pt;
int dist;
};
bool isValid(int row, int col, int x, int y)
{
return (row >= 0) && (row < x) && (col >= 0) && (col < y);
}
bool isSafe(vector<vector<char>> maze, vector<vector<int>> visited, int x, int y)
{
if (maze[x][y] == 'x' || visited[x][y] || maze[x][y] == NULL)
return false;
else
return true;
}
int rowNum[] = { -1, 0, 0, 1 };
int colNum[] = { 0, -1, 1, 0 };
int solveMaze(vector<vector<char>> maze, Point src, Point dest, int rows, int columns)
{
string route;
if (!maze[src.x][src.y] || !maze[dest.x][dest.y])
return -1;
auto visited = vector<vector<int>>(rows, vector<int>(columns));
// Mark the source cell as visited
visited[src.x][src.y] = true;
// Create a queue for solveMaze
queue<queueNode> q;
// Distance of source cell is 0
queueNode s = { src, 0 };
q.push(s); // Enqueue source cell
// Do a solveMaze starting from source cell
while (!q.empty())
{
queueNode curr = q.front();
Point pt = curr.pt;
// If we have reached the destination cell,
// we are done
if (pt.x == dest.x && pt.y == dest.y)
{
route.resize(curr.dist);
cout << "Shortest route is: " << route << endl;
return curr.dist;
}
// Otherwise dequeue the front
// cell in the queue
// and enqueue its adjacent cells
q.pop();
for (int i = 0; i < 4; i++)
{
int row = pt.x + rowNum[i];
int col = pt.y + colNum[i];
// if adjacent cell is valid, has path and
// not visited yet, enqueue it.
if (isValid(row, col, rows, columns) && maze[row][col] && !visited[row][col] && isSafe(maze,visited,row,col))
{
switch (i)
{
case 0:
route.append("N");
break;
case 1:
route.append("W");
break;
case 2:
route.append("E");
break;
case 3:
route.append("S");
break;
}
visited[row][col] = true;
queueNode Adjcell = { {row, col},curr.dist + 1 };
q.push(Adjcell);
}
}
}
return -1;
}
int main()
{
string filename;
int rows;
int columns;
cout << "Please input the name of your maze!" << endl;
cin >> filename;
cout << endl;
cout << "Please input the amount of rows in your maze!" << endl;
cin >> rows;
cout << endl;
cout << "Please input the amount of columns in your maze!" << endl;
cin >> columns;
cout << endl;
int startRow = 0;
int startColumn = 0;
int endRow = 0;
int endColumn = 0;
int column = 0;
auto maze = vector<vector<char>>(rows,vector<char>(columns));
ifstream input(filename);
char data = input.get();
while (!input.eof())
{
for (int row = 0; row < rows; row++)
{
while (data != '\n' && !input.eof())
{
if (data == 'A')
{
startRow = row;
startColumn = column;
}
if (data == 'B')
{
endRow = row;
endColumn = column;
}
maze[row][column] = data;
column++;
data = input.get();
}
column = 0;
data = input.get();
}
}
input.close();
cout << "The Maze being solved is: " << endl;
for (int y = 0; y < rows; y++)
{
for (int x = 0; x < columns; x++)
{
cout << maze[y][x];
}
cout << endl;
}
Point source = { startRow, startColumn };
Point dest = { endRow, endColumn };
int dist = solveMaze(maze, source, dest,rows,columns);
if (dist != -1)
cout << "Shortest Path is " << dist;
else
cout << "Shortest Path doesn't exist";
return 0;
}
在我看来，您在 BFS 期间向路由附加了一个字符。这不会 return 正确的最短路径，因为代码需要验证哪个方向实际对应于最短路径。通过在实际测试路径是否是 最短 路径的一部分之前向路径添加方向，输出实际上只是告诉我们 BFS 本身的执行路径。
为了解决这个问题，我们使用了一个父数组，它保留了每个节点的父节点（当您第一次访问相邻单元格时，将该单元格的父节点设置为当前单元格）。广度优先搜索完成后，将“tracer”变量设置为目标，并使用父数组向后跟踪，直到到达起点。请注意，最后的这个“路径重建”以逆序重建路径（因为我们从目的地迭代回到起点）。
这是我实现这种方法的代码：
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
void bfs(vector <vector<char>> &grid, int R, int C, int sR, int sC, int eR, int eC){
vector <vector<bool>> visited(R, vector <bool> (C, false));
map <pair<int, int>, pair <int, int>> parent;
queue <pair<int, int>> Q;
Q.push({sR, sC});
visited[sR][sC] = true;
parent[{sR, sC}] = {sR, sC}; // it doesn't really matter what you set it to
while(!Q.empty()){
int r = Q.front().first, c = Q.front().second;
Q.pop();
if(r == eR && c == eC){
break;
}
// enqueue all "valid" (unvisited, not-a-wall) adjacent squares
if(r > 0 && !visited[r-1][c] && grid[r-1][c] != 'x'){
visited[r-1][c] = true;
parent[{r-1, c}] = {r, c};
Q.push({r-1, c});
}
if(r < R-1 && !visited[r+1][c] && grid[r+1][c] != 'x'){
visited[r+1][c] = true;
parent[{r+1, c}] = {r, c};
Q.push({r+1, c});
}
if(c > 0 && !visited[r][c-1] && grid[r][c-1] != 'x'){
visited[r][c-1] = true;
parent[{r, c-1}] = {r, c};
Q.push({r, c-1});
}
if(c < C-1 && !visited[r][c+1] && grid[r][c+1] != 'x'){
visited[r][c+1] = true;
parent[{r, c+1}] = {r, c};
Q.push({r, c+1});
}
}
if(visited[eR][eC] == false){
cout << "The destination was unreachable from the source." << endl;
return;
}
// trace back from the destination to the start
pair <int, int> tracer = {eR, eC};
vector <char> path;
// note that this loop constructs the path in reverse order because
// we iterate from the end back to the start
while(tracer != make_pair(sR, sC)){
pair <int, int> next = parent[tracer];
if(next.first - tracer.first == 1){
path.push_back('N');
}
else if(next.first - tracer.first == -1){
path.push_back('S');
}
else if(next.second - tracer.second == 1){
path.push_back('L');
}
else if(next.second - tracer.second == -1){
path.push_back('R');
}
tracer = next;
}
cout << "Shortest Path Length: " << path.size() << endl;
// we print this in reverse order (see the above comment)
for(int i = path.size()-1; i >= 0; --i){
cout << path[i];
}
cout << endl;
}
int main()
{
int R, C, sR, sC, eR, eC;
cin >> R >> C;
vector <vector<char>> grid(R, vector <char> (C));
for(int i = 0; i < R; ++i){
for(int j = 0; j < C; ++j){
cin >> grid[i][j];
if(grid[i][j] == 'A'){
sR = i;
sC = j;
}
else if(grid[i][j] == 'B'){
eR = i;
eC = j;
}
}
}
// Input Done
bfs(grid, R, C, sR, sC, eR, eC);
return 0;
}