200.岛屿数量

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1

示例 2:
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

方法

每遍历矩阵中的一个值，进入到感染函数中去，感染函数会把连在一块的1全部变成2。感染过程完成后，岛数量加1（初始为0）。之后遍历过程中如果是2或0直接跳过，直到再遇到1时进入感染过程。

代码

public int numIslands(char[][] m) {
    if (m == null || m.length == 0) {
        return 0;
    }
    int N = m.length;
    int M = m[0].length;
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (m[i][j] == '1') {
                res++;
                infect(m, i, j, N, M);
            }
        }
    }
    return res;
}

public static void infect(char[][] m, int i, int j, int N, int M) {
    //只当一个位置为1时才进行感染过程
    if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != '1') {
        return;
    }
    m[i][j] = '2';
    infect(m, i + 1, j, N, M);
    infect(m, i - 1, j, N, M);
    infect(m, i, j + 1, N, M);
    infect(m, i, j - 1, N, M);
}