DFS

BFS

LeetCode

934. 最短的桥

二维数组中存在两座岛屿（1表示陆地，0表示水），现在可以将0翻转1，求使得两座岛屿连接起来需要翻转0的最小数目。

  1. class Node {
  2.     int r;
  3.     int c;
  4.     public Node(int r, int c) {
  5.         this.r = r;
  6.         this.c = c;
  7.     }
  8. }
  9. private int rows;
  10. private int cols;
  11. //上下左右
  12. private int[] dirR = {-1, 1, 0, 0};
  13. private int[] dirC = {0, 0, -1, 1};
  14. private Queue<Node> queue = new LinkedList();
  16. public int shortestBridge(int[][] A) {
  17.     rows = A.length;
  18.     cols = A[0].length;
  19.     boolean isFindFirst = false;
  20.     //第一座岛屿染色
  21.     for (int i = 0; i < rows; i++) {
  22.         for (int j = 0; j < cols; j++) {
  23.             if (A[i][j] == 0)   continue;
  25.             dfs(A, i, j);
  26.             isFindFirst = true;
  27.             break;
  28.         }
  29.         if (isFindFirst)    break;
  30.     }
  31.     // bfs扩散寻找第二座岛屿
  32.     int step = 0;
  33.     while (!queue.isEmpty()) {
  34.         int size = queue.size();
  35.         while (size-- > 0) {
  36.             Node node = queue.poll();
  37.             for (int i = 0; i < dirR.length; i++) {
  38.                 int nextR = node.r + dirR[i], nextC = node.c + dirC[i];
  39.                 if (!isInArea(nextR, nextC) || A[nextR][nextC] == 2)    continue;
  41.                 if (A[nextR][nextC] == 1)    return step;
  43.                 A[nextR][nextC] = 2;
  44.                 queue.offer(new Node(nextR, nextC));
  45.             }
  46.         }
  47.         step++;
  48.     }
  49.     return step;
  50. }
  52. private boolean isInArea(int i, int j) {
  53.     return i >= 0 && i < rows && j >= 0 && j < cols;
  54. }
  55. private void dfs(int[][] graph, int r, int c) {
  56.     queue.offer(new Node(r, c));
  57.     graph[r][c] = 2;
  58.     for (int i = 0; i < dirR.length; i++) {
  59.         int nextR = r + dirR[i], nextC = c + dirC[i];
  60.         if (!isInArea(nextR, nextC) || graph[nextR][nextC] != 1)    continue;
  62.         dfs(graph, nextR, nextC);
  63.     }
  64. }

首先找到第一座岛（dfs），然后从第一座岛屿开始扩散到第二座岛屿（bfs）。