Click here to Skip to main content
15,399,959 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
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);
}
Posted
Updated 14-Oct-21 14:44pm
Comments
Rick York 14-Oct-21 18:42pm
   
I have two recommendations for you. First, put your input data into a file and then run your program with stdin redirected from that file. The syntax for that will be something like "YourProgram < InputFile.txt". This will much easier than typing it all in every time. Personally, I forgo manual entry almost always and read files for input but that's just me. Second, have a look at the column titled "Related Questions" on the right of the page. This question has been asked before so some of the previous answers might be helpful.
Izzy 2021 15-Oct-21 4:41am
   
Thank you!
Shao Voon Wong 14-Oct-21 22:25pm
   
https://www.codeproject.com/Articles/5254765/Lee-Algorithm-Mazesolver
Izzy 2021 15-Oct-21 4:41am
   
Thank you!

1 solution

Someone else may have the patience to decipher your uncommented code, but I don't. I'll just explain how I'd do it and leave the rest up to you.

1. Reaching the start square requires 0 moves, so set its distance=0 and n=0.
2. Set each of the other squares to distance=-1.
3. Start an iteration that increments n after each pass (step 4).
4. For each square at distance n, look at its adjacent squares. For each one that is at distance -1, set its distance to n+1 and record the direction taken from the square at distance n. If this square is also the goal, stop and output the solution by backtracking through the recorded directions.
5. If no new squares were reached while looking at all the squares at distance n, no solution exists.
   
v2
Comments
Jon McKee 14-Oct-21 21:22pm
   
To add onto this, check out the A* search algorithm. It operates much the same but a bit smarter so it can handle larger m x n matrices.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900