How to use a breadth first search to solve shortest path in maze

See more:

C++11

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);
          
        }
    }
  } // end while loop

  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);
}