leetcode

0 class Solution {

1 int m, n;

2 vector<int> ox = {-1, 1, 0, 0};

3 vector<int> oy = {0, 0, -1, 1};

4

5 bool is_valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }

6

7 bool is_exit(int x, int y) { return x == 0 || x == m - 1 || y == 0 || y == n - 1; }

8

9 public:

10 int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) {

11 m = maze.size();

12 n = maze[0].size();

13

14 queue<pair<int, int>> q;

15 q.push({entrance[0], entrance[1]});

16 for (int lvl = 0; !q.empty(); lvl++) {

17 for (int t = q.size(); t > 0; t--) {

18 int x = q.front().first;

19 int y = q.front().second;

20 q.pop();

21

22 // cout << x << " " << y << endl;

23

24 if (maze[x][y] == '+') continue;

25

26 if ((x != entrance[0] || y != entrance[1]) && is_exit(x, y)) return lvl;

27

28 maze[x][y] = '+';

29

30 for (int i = 0; i < 4; i++) {

31 int nx = x + ox[i];

32 int ny = y + oy[i];

33 if (is_valid(nx, ny) && maze[nx][ny] != '+') q.push({nx, ny});

34 }

35 }

36 }

37

38 return -1;

39 }

40 };