I am creating a program that will find the shortest Route through a maze and output the Route as a string. I have utilised BFS to find the shortest amount of moves, now I need to output what these moves are. Within my code I have tried to use a switch statement to add characters to the string as it solves the Maze. It utilised the value from a for loop but this was unsuccessful. I also tried to create 2 different switches, one that would check the row int and one that would check the col int. However, this was also unsuccessful.
I can solve some mazes such as:
xxxxx
x...B
A...x
xxxxx
This correctly outputs:
Shortest route is: ENEEE
Shortest Path is 5
However, another maze I am trying to solve is:
xxxxxxxxxx
x........x
x..xxxx..x
x..xxxx..x
A..xxxx..B
x..xxxx..x
x........x
x........x
xxxxxxxxxx
This results in an output of:
Shortest route is: ENESNESSNESSE
Shortest Path is 13
Whilst the distance is correct, the route itself isn't. If anyone could spot something that I am missing please let me know.
Please find my code below:
#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;
}
It looks to me like you're appending a char to the route during your BFS. This will not return the correct shortest path because the code needs to validate which direction actually corresponds with the shortest path. By adding directions to the path before actually testing if it's part of the shortest path, the output really just tells us the path of execution for the BFS itself.
To solve this, we use a parent array, which keeps every node's parent (when you first visit an adjacent cell, set that cell's parent to the current cell). After the breadth-first search completes, set a "tracer" variable to the destination and use the parent array to trace backwards until you reach the start. Note that this "path reconstruction" at the end reconstructs the path in reverse order (because we iterate from the destination back to the start).
Here's my code implementing this approach:
#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;
}