leetcode

0 class Solution {

1 static const constexpr int offs_x[] = {1, 0, -1, 0};

2 static const constexpr int offs_y[] = {0, 1, 0, -1};

3

4 int n;

5

6 bool valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < n; }

7

8 public:

9 int shortestBridge(vector<vector<int>> &grid) {

10 queue<pair<int, int>> dq1, dq2;

11 n = grid.size();

12

13 for (int i = 0; i < n; i++) {

14 for (int j = 0; j < n; j++) {

15 if (!grid[i][j]) continue;

16 dq1.push({i, j});

17 grid[i][j] = 2;

18 goto parse;

19 }

20 }

21

22 return -1;

23

24 parse:

25 while (!dq1.empty()) {

26 auto [i, j] = dq1.front();

27 dq1.pop();

28 for (int k = 0; k < 4; k++) {

29 int a = i + offs_x[k], b = j + offs_y[k];

30 if (!valid(a, b)) continue;

31 if (grid[a][b] == 1)

32 dq1.push({a, b});

33 else if (grid[a][b] == 0)

34 dq2.push({a, b});

35 grid[a][b] = 2;

36 }

37 }

38

39 for (int lvl = 1; !dq2.empty(); lvl++) {

40 for (int k = dq2.size(); k > 0; k--) {

41 auto [i, j] = dq2.front();

42 dq2.pop();

43 for (int k = 0; k < 4; k++) {

44 int a = i + offs_x[k], b = j + offs_y[k];

45 if (!valid(a, b)) continue;

46 if (grid[a][b] == 1)

47 return lvl;

48 else if (grid[a][b] == 0)

49 dq2.push({a, b});

50 grid[a][b] = 2;

51 }

52 }

53 }

54

55 return -1;

56 }

57 };