Leetcode:200. 岛屿数量

题目描述

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

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

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

示例 1:

输入:
11110
11010
11000
00000
输出: 1
示例 2:

输入:

11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

思路

思路1 DFS

在先判断是否是岛屿之后使用DFS对为’1’的岛屿进行深度优先遍历，将状态改为’0’

TODO

并查集和BFS

代码

class Solution {
    private int[][] paths = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0){
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int result = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if (grid[i][j] == '1'){
                    result += 1;
                }
                dfs(grid, i, j);
            }
        }
        return result;
    }
    
    private void dfs(char[][] grid, int i, int j){
        if(grid[i][j] == '0'){
            return;
        }
        int m = grid.length;
        int n = grid[0].length;
        grid[i][j] = '0';
        for(int[] path: paths){
            int x = i + path[0];
            int y = j + path[1];
            if (x >= 0 && x < m && y >= 0 && y < n){
                if (grid[x][y] == '1'){
                    dfs(grid, x, y);
                }
            }
        }
    }
}