[数据结构与算法]#200 Number of Islands

Description

Given an m x n 2D binary grid grid which represents a map of '1’s (land) and '0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Examples

Example 1:

Input: grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
Output: 1

Example 2:

Input: grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is ‘0’ or ‘1’.

思路

感觉就是一个深度优先搜索的问题，一开始时候有点钻牛角尖了，觉得要往一个方向走完了再去别的方向，后来想了一下，觉得递归的流程里面其实已经包含了相关的判断了，我再写在循环里面只会增加比较和运算次数，所以总结如下两个代码

代码

class Solution {
    char[][] matrix;
    
    public void setZeros(int x, int y){
        int max_x = matrix.length;
        int max_y = matrix[0].length;
        if (x >= max_x || y >= max_y || x < 0 || y < 0)
            return;
        
        int tmp_x = x + 1, tmp_y = y;
        while(tmp_x < max_x && matrix[tmp_x][tmp_y] == '1') {
            matrix[tmp_x][tmp_y] = '0';
            setZeros(tmp_x, tmp_y);
            tmp_x ++;
        }
        
        tmp_x = x - 1;
        while(tmp_x >= 0 && matrix[tmp_x][tmp_y] == '1') {
            matrix[tmp_x][tmp_y] = '0';
            setZeros(tmp_x, tmp_y);
            tmp_x --;
        }
        
        tmp_x = x;
        tmp_y = y + 1;
        while(tmp_y < max_y && matrix[tmp_x][tmp_y] == '1') {
            matrix[tmp_x][tmp_y] = '0';
            setZeros(tmp_x, tmp_y);
            tmp_y ++;
        }
        
        tmp_y = y - 1;
        while(tmp_y >= 0 && matrix[tmp_x][tmp_y] == '1') {
            matrix[tmp_x][tmp_y] = '0';
            setZeros(tmp_x, tmp_y);
            tmp_y --;
        }
    }
    
    public int numIslands(char[][] grid) {
        int count = 0;
        matrix = new char[grid.length][grid[0].length];
        
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                matrix[i][j] = grid[i][j];
            }
        } 
        
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                if (matrix[i][j] == '1'){
                    matrix[i][j] = '0';
                    setZeros(i, j);
                    count ++;
                }
            }
        } 
        
        return count;
    }
}

class Solution {
    char[][] matrix;
    
    public void setZeros(int x, int y){
        int max_x = matrix.length;
        int max_y = matrix[0].length;
        if (x >= max_x || y >= max_y || x < 0 || y < 0 || matrix[x][y] != '1' )
            return;
        
        matrix[x][y] = '0';
        setZeros(x + 1, y);
        setZeros(x - 1, y);
        setZeros(x, y + 1);
        setZeros(x, y - 1);
        
    }
    
    public int numIslands(char[][] grid) {
        int count = 0;
        matrix = new char[grid.length][grid[0].length];
        
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                matrix[i][j] = grid[i][j];
            }
        } 
        
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                if (matrix[i][j] == '1'){
                    setZeros(i, j);
                    count ++;
                }
            }
        } 
        
        return count;
    }
}