代码随想录——图论一刷day03

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

`

---

一、力扣130. 被围绕的区域

class Solution {
    boolean[][] flag;
    int[][] move = {
        {0,1},
        {0,-1},
        {-1,0},
        {1,0}
    };
    public void solve(char[][] board) {
        flag = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i ++){
            if(board[i][0] == 'O' && flag[i][0] == false){
                dfs(board, i, 0);
            }
            if(board[i][board[0].length-1] == 'O' && flag[i][board[0].length-1] == false){
                dfs(board, i, board[0].length-1);
            }
        }
        for(int i = 0; i < board[0].length; i ++){
            if(board[0][i] == 'O' && flag[0][i] == false){
                dfs(board, 0, i);
            }
            if(board[board.length-1][i] == 'O' && flag[board.length-1][i] == false){
                dfs(board, board.length-1, i);
            }
        }
        for(int i = 0; i < board.length; i ++){
            for(int j = 0; j < board[0].length; j ++){
                if(board[i][j] == 'O' && flag[i][j] == false){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board, int x, int y){
        flag[x][y] = true;
        for(int i = 0; i < 4; i ++){
            int nextX = x + move[i][0];
            int nextY = y + move[i][1];
            if(nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board[x].length || flag[nextX][nextY] == true || board[nextX][nextY] == 'X'){
                continue;
            }
            dfs(board, nextX, nextY);
        }
    }
    
}
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

二、力扣417. 太平洋大西洋水流问题

class Solution {
    int[][] move = {{0,1},{0,-1},{-1,0},{1,0}};
    boolean[][][] flag;
    // boolean[][] visited;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int row = heights.length, col = heights[0].length;
        flag = new boolean[row][col][2];
        // visited = new boolean[row][col];
        for(int i = 0; i < row; i ++){
            if(flag[i][0][0] == false){
                dfs(heights, i, 0, 0);
            }
            if(flag[i][col-1][1] == false){
                dfs(heights, i, col-1, 1);
            }
        }
        for(int i = 0; i < col; i ++){
            if(flag[0][i][0] == false){
                dfs(heights, 0, i, 0);
            }
            if(flag[row-1][i][1] == false){
                dfs(heights, row-1, i, 1);
            }
        }
        for(int i = 0; i < row; i ++){
            for(int j = 0; j < col; j ++){
                if(flag[i][j][0] == true && flag[i][j][1] == true){
                    res.add(Arrays.asList(i,j));
                }
            }
        }
        return res;
    }
    public void dfs(int[][] heights, int x, int y, int t){
        if(t == 0){
            flag[x][y][0] = true;
        }else{
            flag[x][y][1] = true;
        }
        for(int i = 0; i < 4; i ++){
            int nextX = x + move[i][0];
            int nextY = y + move[i][1];
            if(nextX < 0 || nextX >= heights.length || nextY < 0 || nextY >= heights[x].length || heights[nextX][nextY] < heights[x][y]){
                continue;
            }
            if(t == 0 && flag[nextX][nextY][0]){
                continue;
            }
            if(t == 1 && flag[nextX][nextY][1]){
                continue;
            }
            dfs(heights, nextX, nextY, t);
        }
    }
}
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

三、力扣827. 最大人工岛

class Solution {
    int[][] move = {{0,1},{0,-1},{-1,0},{1,0}};
    int count;
    public int largestIsland(int[][] grid) {
        int res = 0;
        int path = 0;
        int mark = 1;
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(grid[i][j] == 1){
                    count = 0;
                    mark ++;
                    dfs1(grid, i, j, mark);
                    map.put(mark,count);
                    res = Math.max(res,count);
                }
            }
        }
        for(int i = 0; i < grid.length; i ++){
            for(int j = 0; j < grid[0].length; j ++){
                if(grid[i][j] == 0){
                    Set<Integer> set = new HashSet<>();
                    path = 0;
                    for(int t = 0; t < 4; t ++){
                        int nextX = i + move[t][0];
                        int nextY = j + move[t][1];
                        if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length ||grid[nextX][nextY] == 0){
                            continue;
                        }
                        set.add(grid[nextX][nextY]);
                    }
                    for(Integer in : set){
                        path += map.get(in);
                    }
                    path += 1;
                    res = Math.max(res, path);
                }
            }
        }
        return res;
    }
    public void dfs1(int[][] grid, int x, int y, int mark){
        count ++;
        grid[x][y] = mark;
        for(int i = 0; i < 4; i ++){
            int nextX = x + move[i][0];
            int nextY = y + move[i][1];
            if(nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length || grid[nextX][nextY] == 0 || grid[nextX][nextY] == mark){
                continue;
            }
            dfs1(grid, nextX, nextY, mark);
        }
    }
}
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