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.

Example 1:

11110
11010
11000
00000
Answer: 1

Example 2:

11000
11000
00100
00011
Answer: 3

思路: 找被分隔开的连续的’1’,每当遇到’1’后,就BFS或DFS往四个方向找, 直到遇到’0’位置。 然后把这个点给记录下来。 为了不改动给定数组,我们生成一个visited数组来标记找过的1的值都为true. 遍历的时候注意边界条件的检查

DFS:

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0] == null) return 0;
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                explore(i, j, row, col, grid, visited); // DFS explore grid[i][j]
                count++;
            }
        }
        return count;
    }

    public void explore(int i, int j, int row, int col, char[][] grid, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == '0'|| visited[i][j]) return;
        // mark this point
        visited[i][j] = true;
        explore(i - 1, j, row, col, grid, visited); // visit left
        explore(i + 1, j, row, col, grid, visited); // visit right
        explore(i, j + 1, row, col, grid, visited); // visit up
        explore(i, j - 1, row, col, grid, visited); // visit down
    }
}

BFS的话,用Queue来实现, 对坐标x,y需要进行封装一下用Point(x,y)来操作会方便很多. 遇到’1’的点,先压入queue里面;如果queue不为空,取出queue中的点,判断四周的点是否是在范围的点,如果是范围内并且为’1’的点,就放入queue中。

public class Solution {
    class Point {
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public int[] xDir = new int[]{-1, 0, 1, 0};
    public int[] yDir = new int[]{0, -1, 0, 1};

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0 || grid[0] == null) return 0;
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];

        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                explore(i, j, row, col, grid, visited); // DFS explore grid[i][j]
                count++;
            }
        }
        return count;
    }

    public void explore(int i, int j, int row, int col, char[][] grid, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == '0'|| visited[i][j]) return;
        ArrayDeque<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(i,j));
        while(!queue.isEmpty()) {
            Point point = queue.poll();
            for (int k = 0; k < 4; k++) {
                int newX = point.x + xDir[k];
                int newY = point.y + yDir[k];
                if(shouldExplore(newX, newY, row, col, grid, visited)) {
                    visited[newX][newY] = true;
                    queue.offer(new Point(newX, newY));
                }
            }
        }
    }

    public boolean shouldExplore(int i, int j, int row, int col, char[][] grid, boolean[][] visited) {
         if (i < 0 || j < 0 || i >= row || j >= col || grid[i][j] == '0'|| visited[i][j]) return false;
         return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s