Nearest Exit from Entrance in Maze LeetCode solution in C++

1
class Solution {
2
 public:
3
  // checks if the coordinates of the cell are that of an unvisited valid empty
4
  // cell
5
  bool isValid(int x, int y, int n, int m, vector<vector<char>> &maze,
6
               vector<vector<int>> &visited) {
7
    if (x >= 0 && x < n && y >= 0 && y < m && maze[x][y] != '+' && visited[x][y] != 1) {
8
      return true;
9
    }
10
    return false;
11
  }
12

13
  // checks if the cell is a valid exit point
14
  bool isExit(int x, int y, int startX, int startY, vector<vector<char>> &maze,
15
              vector<vector<int>> &visited) {
16
    if (x == startX && y == startY) return false;
17
    if ((x == 0 || x == maze.size() - 1 || y == 0 || y == maze[0].size() - 1) &&
18
        maze[x][y] != '+') {
19
      return true;
20
    }
21
    return false;
22
  }
23

24
  // main BFS function
25
  int bfsHelper(vector<vector<char>> &maze, vector<vector<int>> &visited, int startX, int startY) {
26
    queue<vector<int>> Queue;
27
    Queue.push({startX, startY, 0});
28
    while (!Queue.empty()) {
29
      int x = Queue.front()[0];
30
      int y = Queue.front()[1];
31
      int steps = Queue.front()[2];
32
      Queue.pop();
33
      // if you reach a valid exit, return the number of steps
34
      if (isExit(x, y, startX, startY, maze, visited)) return steps;
35
      int dx[4] = {0, -1, 0, 1};
36
      int dy[4] = {-1, 0, 1, 0};
37
      // check in the 4 directions that you can travel
38
      for (int i = 0; i < 4; i++) {
39
        int newX = x + dx[i], newY = y + dy[i];
40
        // if the coordinates of the cell are that of
41
        // an unvisited valid empty cell, add it to the queue
42
        // and mark it as visited.
43
        if (isValid(newX, newY, maze.size(), maze[0].size(), maze, visited)) {
44
          Queue.push({newX, newY, steps + 1});
45
          visited[newX][newY] = 1;
46
        }
47
      }
48
    }
49
    // if you could not find a valid exit point, return -1
50
    return -1;
51
  }
52

53
  int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) {
54
    int n = maze.size();
55
    int m = maze[0].size();
56
    // create a 2d matrix and mark all the cells as -1,
57
    // denoting that they have not been visited yet.
58
    vector<vector<int>> visited(n, vector<int>(m, -1));
59
    return bfsHelper(maze, visited, entrance[0], entrance[1]);
60
  }
61
};