[leetcode]200. Number of Islands岛屿个数

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.

Input:

11110

11010

11000

00000

Output: 1

Input:

11000

11000

00100

00011

Output: 3

思路：

- DFS and flip the bit-1 on the grid to 0 as we go: to 4 different directions
- Loop through all positions
- Visited spots won't be visited again because they are updated to '0'

怎样check 当前这格是否被visited过？

1.开一个boolean[][] sized as the original input matrix. 但需要额外空间

2.directly flag ‘2’ or ‘0’ (any char excpet ‘1’) in the original input matrix 插个小旗flag一下

代码：

class Solution {

     public int numIslands(char[][] grid) {

        if ( (grid.length==0) || (grid[0].length==0) ) return 0;

        int count =0;

        for (int i = 0; i<grid.length;i++) {

            for (int j=0;j<grid[i].length;j++) {

                if (grid[i][j]=='1') {

                    count++;

                    helper(grid, i, j);

                }

            }

        }

        return count;

    }

    private void helper(char[][] grid, int i, int j) {

        if ((i<0) || (j<0) || (i>=grid.length) || (j>=grid[0].length)

           || grid[i][j] != '1' ) return;

        grid[i][j] = '0'; // mark visited spot

        helper(grid, i+1, j);

        helper(grid, i-1, j);

        helper(grid, i, j+1);

        helper(grid, i, j-1);

    }

}

巴特西

[leetcode]200. Number of Islands岛屿个数

最新文章

热门文章