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
| class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int R = maze.size(), C = maze[0].size();
int r = entrance[0], c = entrance[1];
int ds[] = {1, 0, -1, 0, 1};
vector<vector<bool>> vis(R, vector<bool>(C, false));
queue<pair<int, int>> q;
q.emplace(r, c);
vis[r][c] = true;
int steps = 0;
while (!q.empty()) {
++steps;
int size = q.size();
while (size--) {
auto [cr, cc] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nr = cr + ds[i], nc = cc + ds[i + 1];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || maze[nr][nc] == '+' || vis[nr][nc]) continue;
if (nr == R - 1 || nc == C - 1 || nr == 0 || nc == 0) return steps;
q.emplace(nr, nc);
vis[nr][nc] = true;
}
}
}
return -1;
}
};
|