题目

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

数据

  1. 示例 1:
  2. 输入:
  3. 11110
  4. 11010
  5. 11000
  6. 00000
  7. 输出: 1
  9. 示例 2:
  10. 输入:
  11. 11000
  12. 11000
  13. 00100
  14. 00011
  15. 输出: 3
  16. 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成

解题思路

used ：哈希集合，用于判断节点是否入过队列；当节点加入队列时，同时将节点信息加入哈希集
numIslands ：两层循环判断是否节点已经加入过队列，如果没有： nums++ ，把当前节点的下标传入 BFS ，加入哈希集 used
BFS ：创建队列来进行广度优先搜索：队列头部的上下左右四个相邻节点是否满足条件，满足则加入队列和 used ，然后队列头部节点出队

代码

  1. package DataStructure;
  4. import java.util.HashSet;
  5. import java.util.LinkedList;
  6. import java.util.Queue;
  7. import java.util.Set;
  9. public class BFS {
  10.     /**
  11.      * Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
  12.      * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
  13.      * You may assume all four edges of the grid are all surrounded by water.
  14.      * Input:
  15.      * 11110
  16.      * 11010
  17.      * 11000
  18.      * 00000
  19.      * Output: 1
  20.      *
  21.      * @param grid
  22.      * @return the num of lands
  23.      */
  24.     public int numIslands(char[][] grid) {
  25.         Set<Node> used = new HashSet<>();  //用于判定节点是否加入过队列
  26.         int nums = 0;
  27.         for (int i = 0; i < grid.length; i++) { // 遍历每个节点，如果节点为1并且不在哈希集中，则nums++，并把节点信息传给BFS
  28.             for (int j = 0; j < grid[0].length; j++) {
  29.                 if (grid[i][j] == '1' && !used.contains(new Node(i, j))) {
  30.                     nums++;
  31.                     used.add(new Node(i, j));
  32.                     BFS(grid, i, j, used);
  33.                 }
  34.             }
  35.         }
  36.         return nums;
  37.     }
  39.     /**
  40.      * 为哈希集 used 配置每个节点的信息，存储节点下标
  41.      */
  42.     class Node {
  43.         int x, y;
  45.         public Node(int i, int j) {
  46.             x = i;
  47.             y = j;
  48.         }
  50.         @Override
  51.         public boolean equals(Object obj) {
  52.             if (!(obj instanceof Node))
  53.                 return false;
  54.             if (obj == this)
  55.                 return true;
  56.             return this.x == ((Node) obj).x && this.y == ((Node) obj).y;
  57.         }
  59.         @Override
  60.         public int hashCode() {
  61.             return x + y;
  62.         }
  63.     }
  65.     /**
  66.      * 对于每个队列头节点，遍历其相邻的节点，将所有相连节点加入队列
  67.      *
  68.      * @param grid
  69.      * @param x
  70.      * @param y
  71.      * @param used
  72.      */
  73.     public void BFS(char[][] grid, int x, int y, Set<Node> used) {
  74.         Queue<Node> queue = new LinkedList<>();
  75.         queue.add(new Node(x, y));
  76.         int length = grid.length;
  77.         int width = grid[0].length;
  78.         while (!queue.isEmpty()) { //相邻节点满足没有加入过队列且为陆地则入队，入集合used
  79.             // 右边相邻节点
  80.             int i = queue.peek().x, j = queue.peek().y + 1;
  81.             if (j < width && grid[i][j] == '1' && !used.contains(new Node(i, j))) { //如果右边相邻的是陆地并且不在哈希集中，加入队列，加入哈希集
  82.                 queue.add(new Node(i, j));
  83.                 used.add(new Node(i, j));
  84.             }
  85.             // 下面相邻节点
  86.             i = queue.peek().x + 1;
  87.             j = queue.peek().y;
  88.             if (i < length && grid[i][j] == '1' && !used.contains(new Node(i, j))) { //如果下面相邻的是陆地并且不在哈希集中，加入队列，加入哈希集
  89.                 queue.add(new Node(i, j));
  90.                 used.add(new Node(i, j));
  91.             }
  92.             //左边相邻节点
  93.             i = queue.peek().x;
  94.             j = queue.peek().y - 1;
  95.             if (j >= 0 && grid[i][j] == '1' && !used.contains(new Node(i, j))) {
  96.                 queue.add(new Node(i, j));
  97.                 used.add(new Node(i, j));
  98.             }
  99.             // 上面相邻的节点
  100.             i = queue.peek().x - 1;
  101.             j = queue.peek().y;
  102.             if (i >= 0 && grid[i][j] == '1' && !used.contains(new Node(i, j))) {
  103.                 queue.add(new Node(i, j));
  104.                 used.add(new Node(i, j));
  105.             }
  106.             queue.poll();
  107.         }
  108.     }
  109. }