原题链接:
https://leetcode.cn/problems/number-of-islands/

法1: 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 static int [] dx = new int[]{0,-1,0,1};
    public static int [] dy = new int[]{-1,0,1,0};
    public static int n,m;

    public int numIslands(char[][] grid) {
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        for (int i = 0 ; i < n ; i++){
            for (int j = 0; j < m; j++){
                if (grid[i][j] == '1'){
                    bfs(grid,i,j);
                    ans++;
                }
            }
        }
        return  ans;
    }

    public void bfs(char [][] g,int x,int y){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x,y});
        while (!queue.isEmpty()){
            var t =  queue.poll();
            for (int i = 0 ; i < 4 ; i++){
                int tx = t[0] + dx[i];
                int ty = t[1] + dy[i];
                if (tx < 0 || tx >=n || ty < 0 || ty >= m){
                    continue;
                }

                if (g[tx][ty] == '1'){
                    g[tx][ty] = 'x';
                    queue.offer(new int[]{tx,ty});
                }
            }
        }
    }
}

法2: 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
class Solution {
    public static char [][] g;
    public static int n,m;
    public static int [] dx = new int[]{-1,0,1,0};
    public static int [] dy = new int[]{0,-1,0,1};
    public int numIslands(char[][] grid) {
        g = grid;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        for (int i = 0 ; i < n ; i++){
            for (int j = 0 ; j < m ; j++){
                if (g[i][j] == '1'){
                    dfs(i,j);
                    ans++;
                }
            }
        }

        return ans;
    }

    public void dfs(int x,int y){
        for (int i = 0 ; i < 4 ; i++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= m){
                continue;
            }
            
            if (g[tx][ty] == '1'){
                g[tx][ty] = 'x';
                dfs(tx,ty);
            }
        }
    }
}