200. Number of Islands.md

Solution1 (dfs)

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    count++;
                    dfs(grid, i, j, visited);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        visited[i][j] = true;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == '1' && !visited[x][y]) {
                dfs(grid, x, y, visited);
            }
        }
    }
}

note

• time O(n * m) space O(n * m)
• The idea is to apply depth first search. Skip all 'water'. Once find an 'island', increment the count by 1, and dfs search it until all connected islands are visited. Then proceed with unvisited grids and apply the same idea.