leetcode-number-of-islands

发表于   |   分类于 ，   |  

题目大意

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

　　01矩阵中“小岛”的个数，所谓“小岛”指的是被0包围的1

题目分析

　　简单的BFS即可，DFS或者并查集也能做。

代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public class Solution {
    
    private boolean[] v;
    private int ans;
    
    private boolean check(char[][] grid, int x, int y) {
        int row = grid.length;
        int col = grid[0].length;
        return x >= 0 && x <= row - 1 && y >= 0 && y <= col - 1; 
    }
    
    private void bfs(char[][] grid, int x, int y) {
        int row = grid.length;
        int col = grid[0].length;
        int[] q = new int[row * col];
        q[0] = x * col + y; 
        v[x * col + y] = true;
        int front = 0;
        int rear = 1;
        while (front < rear) {
            int cur = q[front++];
            int i = cur / col;
            int j = cur % col;
            
            for (int dy = -1; dy <= 1; dy += 2) {
                int tmp = i * col + j + dy;
                if (check(grid, i, j + dy) && !v[tmp] && grid[i][j + dy] == '1') {
                    v[tmp] = true;
                    q[rear++] = tmp;
                }
            }
            
            for (int dx = -1; dx <= 1; dx += 2) {
                int tmp = (i + dx) * col + j;
                if (check(grid, i + dx, j) && !v[tmp] && grid[i + dx][j] == '1') {
                    v[tmp] = true;
                    q[rear++] = tmp;
                }
            }
        }
    }
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        v = new boolean[row * col];
        ans = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!v[i * col + j] && grid[i][j] == '1') {
                    ans++;
                    bfs(grid, i, j);
                }
            }
        }
        return ans;
    }
}

　　时间复杂度:O(n*m)