LC934.最短的桥

思路：DFS + BFS

先DFS，把其中一座岛全部变成2
在BFS，以全部为2的岛作为出发点，BFS，到1就停止，返回当前在BFS树上的层次level，就是需要翻转的个数。

注意，为了防止重复访问，需要在BFS入队的时候，将元素进行改变。

代码：

class Solution {
private:
  int dx[4] = {1, 0, -1, 0};
  int dy[4] = {0, 1, 0, -1};
  int row, col;
public:
  bool check(int x, int y) {
      if (0 <= x && x < row && 0 <= y && y < col) {
          return true;
      } 
      return false;
  }
  void dfs(vector<vector<int>>& grid, int x, int y) {
      if (grid[x][y] == 1) {
          grid[x][y] = 2;
          for (int i = 0; i < 4; i++) {
              int nx = x + dx[i], ny = y + dy[i];
              if (check(nx, ny) && grid[nx][ny] == 1) {
                  dfs(grid, nx, ny);
              }
          }
      }
  }
  int shortestBridge(vector<vector<int>>& grid) {
      // 1. DFS，把其中一座岛全部变成2
      // 2. BFS，找到1就停
      row = grid.size(), col = grid[0].size();
      queue<pair<int, int>> q;
      // DFS
      bool once_exc = true;
      for (int i = 0; i < row; i++) {
          for (int j = 0; j < col; j++) {
              if (grid[i][j] == 1 && once_exc) {
                  dfs(grid, i, j);
                  once_exc = false;
              }
          }
      }
      // BFS
      for (int i = 0; i < row; i++) {
          for (int j = 0; j < col; j++) {
              if (grid[i][j] == 2) {
                  q.push({i, j});
              }
          }
      }
      // level 就是BFS上的层次
      int level = 0;
      while (!q.empty()) {
          for (int k = 0, nq = q.size(); k < nq; k ++) {
              int cx = q.front().first, cy = q.front().second;
              q.pop();
              for (int i = 0; i < 4; i++) {
                  int nx = cx + dx[i], ny = cy + dy[i];
                  if (!check(nx, ny)) {
                      continue;
                  }
                  // 返回当前层次
                  if (grid[nx][ny] == 1) {
                      return level;
                  }
                  // 变成3，入队的时候防止重复遍历
                  if (grid[nx][ny] != 2 && grid[nx][ny] != 3) {
                      q.push({nx, ny});
                      grid[nx][ny] = 3;
                  }
              }
          }
          level += 1;
      }
      return -1;
  }
};