Number of Islands

https://leetcode.com/problems/number-of-islands/description/

Given a 2d grid map of '1's (land) and '0's (water), count 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.

Example 1:

11110

11010

11000

00000

Answer: 1

Example 2:

11000

11000

00100

00011

Answer: 3

Thoughts

每次遇到"1", 把它能遍历到的所有"1"都置为0, 以后再遇到"1"说明和之前的不是一个集合的.

Code

class Solution {
    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length, n = m == 0 ? 0 : grid[0].length;
        if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == '1') {
            grid[i][j] = '0';
            for (int[] dir : dirs) {
                dfs(grid, i + dir[0], j + dir[1]);
            }
        }
    }

    public int numIslands(char[][] grid) {
        int m = grid.length, n = m == 0 ? 0 : grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }
}

Analysis

Errors:

1. 必须四个方向都遍历

时间复杂度O(MN)