Question

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

Attention:

由于markdown语法的原因，无法将一行代码添加为代码形式，请在每个Solution类中加入[-1, 0], [1, 0], [0, 1], [0, -1]作为遍历的四个方向。

Thinking:

  • Method：DFS AC
class Solution {    
    public int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int height = grid.length;
        int width = grid[0].length;
        boolean[][] used = new boolean[height][width];
        int count = 0;
        LinkedList<Integer> q = new LinkedList<>();
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(grid[i][j] == '1' && !used[i][j]){
                    count ++;
                    bfs(grid, used, i, j);
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, boolean[][] used, int row, int col){
        if(!(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == '1' && !used[row][col]))
            return;
        used[row][col] = true;
        for(int i = 0; i < 4; i++){
            bfs(grid, used, row + dir[i][0], col + dir[i][1]);
        }
    }
}
  • Method 2: BFS TLE
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        if(grid == null || grid.length == 0) return 0;
        int height = grid.length;
        int width = grid[0].length;
        boolean[][] used = new boolean[height][width];
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                if(grid[i][j] == '0' || used[i][j]) continue;
                else{
                    count++;
                    queue.add(i * width + j);
                    while(!queue.isEmpty()){
                        Integer cnt = queue.poll();
                        int row = cnt / width;
                        int col = cnt % width;
                        used[row][col] = true;
                        for(int p = 0; p < 4; p++){
                            int tempRow = row, tempCol = col;
                            tempRow += dir[p][0];
                            tempCol += dir[p][1];
                            if(tempRow >= 0 && tempRow < height && tempCol >= 0 && tempCol < width && !used[tempRow][tempCol] && grid[tempRow][tempCol] == '1')
                                queue.add(tempRow * width + tempCol);
                        }
                    }
                }
            }
        }
        return count;
    }
}

二刷

  1. 使用bfs 
    class Solution {    
 public int numIslands(char[][] grid) {
     if(grid.length == 0 || grid[0].length == 0) return 0;
     int row = grid.length, col = grid[0].length;
     boolean[][] visited = new boolean[row][col];
     int result = 0;
     for(int i = 0; i < row; i++){
         for(int j = 0; j < col; j++){
             if(grid[i][j] == '1' && !visited[i][j]){
                 visit(grid, row, col, i, j, visited);
                 result ++;
             }
         }
     }
     return result;
 }

 private void visit(char[][] grid, int row, int col, int i, int j, boolean[][] visited){
     visited[i][j] = true;
     int tempRow = 0, tempCol = 0;
     for(int d = 0; d < 4; d++){
         tempRow = i + dir[d][0];
         tempCol = j + dir[d][1];
         if(tempRow >= 0 && tempRow < row && tempCol >= 0 && tempCol < col && grid[tempRow][tempCol] == '1' && !visited[tempRow][tempCol]){
             visit(grid, row, col, tempRow, tempCol, visited);
         }
     }
 }
}