Hello. I would like to find the shortest path in a maze. These are the instructions:
The following input format will come from stdin:
1. The first line will contain 2 integers, m and n, separated by a space. These numbers represent the number of rows and columns in the grid respectively.
2. There will then be m lines each with n columns that represent the maze.
A space represents an open block in the world. You may travel through this block.
An x represents an obstacle. You may not travel through this block.
An S represents the start.
A G represents the goal.
3.The output should be the maze with * characters along the shortest path from the start to the goal. 1 If there is no path between the start and goal, then the output should say "No Path".
May someone please assist?
Thank you.
What I have tried:
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
pair<int, int> getGridSize(string line){
pair<int, int> gridSize;
int start = 0;
int end = line.find(" ");
while (end != -1){
gridSize.first = stoi(line.substr(start, end-start));
start = end + 1;
end = line.find(" ", start);
}
gridSize.second = stoi(line.substr(start, end - start));
return gridSize;
}
vector<vector<char>> getGrid(int rowCount,int colCount){
vector<vector<char>> grid;
string row;
for(int i = 0; i < rowCount; i++){
string line;
getline(cin, line);
vector<char> rowVec(line.begin(), line.end());
grid.push_back(rowVec);
}
return grid;
}
pair<int, int> getPos(vector<vector<char>> grid, int rowCount, int colCount, int charToFind) {
pair<int, int> pos;
for(int i = 0; i < rowCount; i++){
for(int j = 0; j < colCount; j++){
if (grid[i][j] == charToFind){
pos.first = i;
pos.second =j;
return pos;
}
}
}
return pos;
}
void printGrid(int rowCount,int colCount, vector<vector<char>> grid){
for(int i = 0; i < rowCount; i++){
for(int j = 0; j < colCount; j++){
cout << grid[i][j];
}
cout << endl;
}
}
vector<pair<int, int>> getNeighbours(pair<int, int> cell){
pair<int, int> topCell = make_pair(cell.first - 1, cell.second);
pair<int, int> leftCell = make_pair(cell.first, cell.second - 1);
pair<int, int> bottomCell = make_pair(cell.first + 1, cell.second);
pair<int, int> rightCell = make_pair(cell.first, cell.second + 1);
vector<pair<int, int> > neighbours;
neighbours.push_back(leftCell);
neighbours.push_back(rightCell);
neighbours.push_back(topCell);
neighbours.push_back(bottomCell);
return neighbours;
}
bool isMoveValid(vector<vector<char>> grid, int m, int n, pair<int, int> cell){
if (cell.first < 0 || cell.first > m - 1 || cell.second < 0 || cell.first > n -1 || grid[cell.first][cell.second] == 'x'){
return false;
}
return true;
}
void printPath(vector<vector<char>> &grid, vector<pair<int, int>> path, pair<int, int> sourcePos, pair<int, int> goalPos) {
for(pair< int, int> point: path){
if (point.first != sourcePos.first && point.first != goalPos.first && point.second != sourcePos.second && point.second != goalPos.second){
grid[point.first][point.second] = '*';
}
}
}
bool bfs(vector<vector<char>> &grid, pair<int, int> sourcePos, pair<int, int> goalPos, int m, int n){
queue<pair<int, int>> q;
vector<vector<int>> distanceArr;
vector<vector<pair<int, int>>> parentArr;
vector<vector<int>> visited;
for(int i = 0; i <m; i++){
vector<int> visitedVec;
for(int j = 0; j < n; j++){
visitedVec.push_back(0);
}
visited.push_back(visitedVec);
}
for(int i=0; i<n; i++){
vector<int> distanceVec;
vector<pair<int, int>> parentVec;
for (int i = 0; i < n; i++){
parentVec.push_back(make_pair(-2, -2));
distanceVec.push_back(INT_MAX);
}
distanceArr.push_back(distanceVec);
parentArr.push_back(parentVec);
}
visited[sourcePos.first][sourcePos.second] = 1;
q.push(sourcePos);
while (!q.empty() && visited[goalPos.first][goalPos.second] == 0 ){
pair<int, int> curr = q.front();
q.pop();
vector<pair<int, int>> neighbours = getNeighbours(curr);
for(pair<int, int> neighbour : neighbours){
if (isMoveValid(grid, m, n , neighbour) && visited[neighbour.first][neighbour.second] == 0){
visited[neighbour.first][neighbour.second] = 1;
distanceArr[neighbour.first][neighbour.second] = distanceArr[curr.first][curr.second] + 1;
parentArr[neighbour.first][neighbour.second] = curr;
q.push(neighbour);
}
}
}
if (q.empty() && visited[goalPos.first][goalPos.second] == 0) {
cout << "No Path"<<endl;
return false;
}else{
vector<pair<int, int>> path;
pair<int, int> current = goalPos;
while (current.first != sourcePos.first && current.second != sourcePos.second){
path.push_back(current);
current = parentArr[current.first][current.second];
}
path.push_back(sourcePos);
printPath(grid, path, sourcePos, goalPos);
return true;
}
}
int main(){
string line;
getline(cin, line);
pair<int, int> gridSize = getGridSize(line);
int m = gridSize.first;
int n = gridSize.second;
vector<vector<char>> grid = getGrid(m, n);
pair<int, int> sourcePos = getPos(grid, m, n , 'S');
pair<int, int> goalPos = getPos(grid, m, n, 'G');
bfs(grid, sourcePos, goalPos, m, n);
printGrid(m, n, grid);
}