leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1926.cpp (1198B)

      1 class Solution {
      2     int m, n;
      3     vector<int> ox = {-1, 1, 0, 0};
      4     vector<int> oy = {0, 0, -1, 1};
      5 
      6     bool is_valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
      7 
      8     bool is_exit(int x, int y) { return x == 0 || x == m - 1 || y == 0 || y == n - 1; }
      9 
     10   public:
     11     int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) {
     12         m = maze.size();
     13         n = maze[0].size();
     14 
     15         queue<pair<int, int>> q;
     16         q.push({entrance[0], entrance[1]});
     17         for (int lvl = 0; !q.empty(); lvl++) {
     18             for (int t = q.size(); t > 0; t--) {
     19                 int x = q.front().first;
     20                 int y = q.front().second;
     21                 q.pop();
     22 
     23                 // cout << x << " " << y << endl;
     24 
     25                 if (maze[x][y] == '+') continue;
     26 
     27                 if ((x != entrance[0] || y != entrance[1]) && is_exit(x, y)) return lvl;
     28 
     29                 maze[x][y] = '+';
     30 
     31                 for (int i = 0; i < 4; i++) {
     32                     int nx = x + ox[i];
     33                     int ny = y + oy[i];
     34                     if (is_valid(nx, ny) && maze[nx][ny] != '+') q.push({nx, ny});
     35                 }
     36             }
     37         }
     38 
     39         return -1;
     40     }
     41 };