LeetCode link

first thought

  • similar with surrounded problem, using bfs to search.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length < 1 || grid[0].length < 1) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        int[] dirX = {-1, 0, 1, 0};
        int[] dirY = {0, 1, 0, -1};
        int result = 0;
        for (int x = 0; x < row; x++) {
            for (int y = 0; y < col; y++) {
                if (grid[x][y] == '1') {
                    grid[x][y] = '2';
                    queue.add(x * col + y);
                    result++;
                    while (!queue.isEmpty()) {
                        int pos = queue.poll();
                        int posX = pos / col;
                        int posY = pos % col;
                        for (int i = 0; i < 4; i++) {
                            int newX = posX + dirX[i];
                            int newY = posY + dirY[i];
                            if (newX >= 0 && newX < row && newY >= 0 && newY < col && grid[newX][newY] == '1') {
                                grid[newX][newY] = '2';
                                queue.add(newX * col + newY);
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}

result

AC, but the time cost is a little more than DFS