0934.cpp (1669B)
1 class Solution { 2 static const constexpr int offs_x[] = {1, 0, -1, 0}; 3 static const constexpr int offs_y[] = {0, 1, 0, -1}; 4 5 int n; 6 7 bool valid(int i, int j) { return i >= 0 && i < n && j >= 0 && j < n; } 8 9 public: 10 int shortestBridge(vector<vector<int>> &grid) { 11 queue<pair<int, int>> dq1, dq2; 12 n = grid.size(); 13 14 for (int i = 0; i < n; i++) { 15 for (int j = 0; j < n; j++) { 16 if (!grid[i][j]) continue; 17 dq1.push({i, j}); 18 grid[i][j] = 2; 19 goto parse; 20 } 21 } 22 23 return -1; 24 25 parse: 26 while (!dq1.empty()) { 27 auto [i, j] = dq1.front(); 28 dq1.pop(); 29 for (int k = 0; k < 4; k++) { 30 int a = i + offs_x[k], b = j + offs_y[k]; 31 if (!valid(a, b)) continue; 32 if (grid[a][b] == 1) 33 dq1.push({a, b}); 34 else if (grid[a][b] == 0) 35 dq2.push({a, b}); 36 grid[a][b] = 2; 37 } 38 } 39 40 for (int lvl = 1; !dq2.empty(); lvl++) { 41 for (int k = dq2.size(); k > 0; k--) { 42 auto [i, j] = dq2.front(); 43 dq2.pop(); 44 for (int k = 0; k < 4; k++) { 45 int a = i + offs_x[k], b = j + offs_y[k]; 46 if (!valid(a, b)) continue; 47 if (grid[a][b] == 1) 48 return lvl; 49 else if (grid[a][b] == 0) 50 dq2.push({a, b}); 51 grid[a][b] = 2; 52 } 53 } 54 } 55 56 return -1; 57 } 58 };