岛屿数量-LeetCode

岛屿数量

200. 岛屿数量

思路基本上就是深度优先搜索，在搜索路径的时候将路径修改为‘0’值，当然需要看情况，如果不允许修改原数组，我们需要另外new一个同样大小的标记数组来进行记录。

一个需要注意的点就是dfs函数，应该使用形如dfs(grid, row-1, col)这样传参方式，而不应在dfs函数内修改row和col，像这样：row--; dfs(grid, row-1, col)，这样会导致函数在返回的时候，并不会回退，就像下图这种情况：导致右边的1没有被搜索到。

在代码出错的时候，最后将深度优先搜索的信息打印出来，方便调试，否则肉眼调试很难解决问题。

最后用两个for循环遍历数组，对每个遍历到的1都进行dfs搜索，搜索结束就对结果+1，时间复杂度为$O(MN)$，空间复杂度最坏为$O(MN)$，即数组全部为1，需要压$MN$个栈。

class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length, col = grid[0].length;
        if(row == 0 || col == 0)
            return 0;
        int result = 0;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] != '0'){
                    dfs(grid, i, j);
                    result++;
                }
                else 
                    continue;
            }
        }
        return result;
    }
    private void dfs(char[][] grid, int row, int col){
        grid[row][col] = '0'; 
        // System.out.println("[" + row + ", " + col + "]");
        if(row >= 1 && grid[row - 1][col] == '1') { 
            dfs(grid, row-1, col);
        } 
        if(col >= 1 && grid[row][col - 1] == '1') { 
            dfs(grid, row, col-1);
        }
        if(row+1 < grid.length && grid[row + 1][col] == '1') { 
            dfs(grid, row+1, col);
        } 
        if(col+1 < grid[0].length && grid[row][col + 1] == '1') { 
            dfs(grid, row, col+1);
        }
        // System.out.println("result: "+result+" return: ["+row +", "+col+"]");
        return;
    }
}