aboutsummaryrefslogtreecommitdiff
path: root/nearest_exit_maze.cpp
blob: 2e0a4cfc9562fb679465be4d552b11fc7d276e02 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include "leetcode.h"

class Solution {
public:
  int nearestExit(vvd(char) & maze, vector<int> &entrance) {
    int m = maze.size(), n = maze[0].size();
    int dirs[5] = {0, -1, 0, 1, 0};
    auto isExit = [&](int i, int j) -> int {
      return (i != entrance[0] || j != entrance[1]) &&
             (i * j == 0 || i == m - 1 || j == n - 1);
    };
    deque<array<int, 3>> dqa = {{entrance[0], entrance[1], 0}};
    while (!dqa.empty()) {
      auto [i, j, s] = dqa.front();
      dqa.pop_front();
      for (int d = 0; d < 4; ++d) {
        int i2 = i + dirs[d];
        int j2 = j + dirs[d + 1];
        if (i2 < 0 || i2 >= m || j2 < 0 || j2 >= n || maze[i2][j2] == '+')
          continue;
        maze[i2][j2] = '+';
        if (isExit(i2, j2))
          return s + 1;
        dqa.push_back({i2, j2, s + 1});
      }
    }
    return -1;
  }
};

int main() {
  Solution obj;
  vvd(char)
      maze = {{'+', '+', '.', '+'}, {'.', '.', '.', '+'}, {'+', '+', '+', '.'}};
  vector<int> entrance = {1, 2};
  cout << obj.nearestExit(maze, entrance);
}