给一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = {
{1,1,1,1,1},
{1,1,1,1,0},
{1,1,0,0,0},
{0,0,0,0,0}
}
输出：1
示例 2：
输入：grid = {
{1,1,0,0,0},
{1,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,1}
}
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'
package com.loo;
import java.util.LinkedList;
import java.util.Queue;
public class NumberIslands {
public static int[] DX = new int[] {1 , 0 , -1 , 0};
public static int[] DY = new int[] {0 , 1 , 0 , -1};
public static void main(String[] args) {
int[][] grid1 = {
{1,1,1,1,1},
{1,1,1,1,0},
{1,1,0,0,0},
{0,0,0,0,0}
};
int[][] grid2 = {
{1,1,0,0,0},
{1,1,0,0,0},
{0,0,1,0,0},
{0,0,0,1,1}
};
int[][] grid3 = {
{1 , 1 , 1},
{0 , 1 , 0},
{1 , 0 , 0},
{1 , 0 , 1}
};
System.out.println(getNumberIslands1(grid1));
// System.out.println(getNumberIslands1(grid2));
// System.out.println(getNumberIslands2(grid2));
// System.out.println(getNumberIslands3(grid3));
}
// 深度优先。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
// 最终岛屿的数量就是进行深度优先搜索的次数。时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
// 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
public static int getNumberIslands1(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rowLen = grid.length;
int colLen = grid[0].length;
int numbersIsland = 0;
for (int i=0;i<rowLen;i++) {
for (int j=0;j<colLen;j++) {
if (grid[i][j]==1) {
numbersIsland++;
dfs(grid , i , j);
}
}
}
return numbersIsland;
}
public static void dfs(int[][] grid , int x , int y) {
int rowLen = grid.length;
int colLen = grid[0].length;
if (x<0 || x >=rowLen || y<0 || y>= colLen || grid[x][y]==0) {
return;
}
grid[x][y] = 0;
for (int i=0;i<4;i++) {
int tx = x + DX[i];
int ty = y + DY[i];
dfs(grid , tx , ty);
}
}
// 广度优先。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
// 最终岛屿的数量就是进行广度优先搜索的次数。
// 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
// 空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。
public static int getNumberIslands2(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rowLen = grid.length;
int colLen = grid[0].length;
int numbersIsland = 0;
for (int i=0;i<rowLen;i++) {
for (int j=0;j<colLen;j++) {
if (grid[i][j]==1) {
numbersIsland++;
grid[i][j] = 0;
Queue<Integer> neighbors = new LinkedList<Integer>();
neighbors.add(i*colLen + j);
while (!neighbors.isEmpty()) {
int numValue = neighbors.poll();
int x = numValue/colLen;
int y = numValue%colLen;
for (int k=0;k<4;k++) {
int tx = x + DX[k];
int ty = y + DY[k];
if (tx<0 || tx>=rowLen || ty<0 || ty>=colLen || grid[tx][ty] == 0) {
continue;
}
if (grid[tx][ty] == 1) {
grid[tx][ty] = 0;
neighbors.add(tx*colLen + ty);
}
}
}
}
}
}
return numbersIsland;
}
// 并查集。如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。
// 时间复杂度：O(MN * α(MN))，其中 M 和 N 分别为行数和列数。注意当使用路径压缩（见 find 函数）和按秩合并（见数组 rank）实现并查集时，
// 单次操作的时间复杂度为 α(MN)，其中 α(x) 为反阿克曼函数，当自变量 x 的值在人类可观测的范围内（宇宙中粒子的数量）时，
// 函数 α(x) 的值不会超过 5，因此也可以看成是常数时间复杂度。
// 空间复杂度：O(MN)O(MN)，这是并查集需要使用的空间。
public static int getNumberIslands3(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rowLen = grid.length;
int colLen = grid[0].length;
UnionFind union = new UnionFind(grid);
for (int i=0;i<rowLen;i++) {
for (int j=0;j<colLen;j++) {
if (grid[i][j]==1) {
grid[i][j] = 0;
for (int k=0;k<4;k++) {
int tx = i + DX[k];
int ty = j + DY[k];
if (tx<0 || tx>=rowLen || ty<0 || ty>=colLen || grid[tx][ty] == 0) {
continue;
}
if (grid[tx][ty]==1) {
union.union(i*colLen+j, tx*colLen+ty);
}
}
}
}
}
return union.getCount();
}
static class UnionFind {
int count;
int[] parent;
int[] rank;
public UnionFind (int[][] grid) {
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m*n];
rank = new int[m*n];
for (int i=0;i<m;i++) {
for (int j=0;j<n;j++) {
if (grid[i][j]==1) {
parent[i*n+j] = i*n+j;
count++;
}
rank[i*n+j] = 0;
}
}
}
public int find(int i) {
if (parent[i]!=i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
public void union(int x , int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx!=rooty) {
if (rank[rootx]>rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx]<rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx] += 1;
}
count--;
}
}
public int getCount() {
return count;
}
}
}