Leetcode(200) Number of Islands

发表于 | 分类于

Description

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:

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1

Example 2:

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

解法

典型的地图遍历题，这里可以通过BFS和DFS解题。

BFS:

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
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    Queue<node> q = new LinkedList();
                    q.offer(new node(i, j));
                    while (!q.isEmpty()) {
                        node now = q.poll();
                        grid[now.x][now.y] = '0';
                        for (int ii = 0; ii < 4; ii++) {
                            int nextx = now.x + dirx[ii];
                            int nexty = now.y + diry[ii];
                            if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                                if (grid[nextx][nexty] == '1') {
                                    node next = new node(nextx, nexty);
                                    grid[next.x][next.y] = '0';
                                    q.offer(next);
                                }
                            }
                        }
                    }
                    res++;
                }
            }
        return res;
    }
}

class node {
    int x;
    int y;

    node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

特别注意需要再新点入队前将地图中的值置0以避免重复访问死循环！！！

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
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    DFS(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    void DFS(char[][] grid, int x, int y) {
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        if (grid[x][y] == '1') {
            grid[x][y] = 0;
            for (int i = 0; i < 4; i++) {
                int nextx = x + dirx[i];
                int nexty = y + diry[i];
                if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                    if (grid[nextx][nexty] == '1') {
                        DFS(grid, nextx, nexty);
                    }
                }
            }
        }
        return;
    }
}

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
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    DFS(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    void DFS(char[][] grid, int x, int y) {
        int[] dirx = {1, -1, 0, 0};
        int[] diry = {0, 0, 1, -1};
        Stack<node> s = new Stack<>();
        s.push(new node(x, y));
        grid[x][y] = '0';
        while (!s.isEmpty()) {
            node tmp = s.peek();
            int flag = 0;
            for (int i = 0; i < 4; i++) {
                int nextx = tmp.x + dirx[i];
                int nexty = tmp.y + diry[i];
                if (nextx >= 0 && nextx < grid.length && nexty >= 0 && nexty < grid[0].length) {
                    if (grid[nextx][nexty] == '1') {
                        grid[nextx][nexty] = '0';
                        s.push(new node(nextx, nexty));
                        flag = 1;
                    }
                }
            }
            if (flag == 0) {
                s.pop();
            }
        }
        return;
    }
}

class node {
    int x;
    int y;

    node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

同样注意标0的时机。