代码随想录图论|130. 被围绕的区域 417太平洋大西洋水流问题

130. 被围绕的区域

**题目：**给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
题目链接：130. 被围绕的区域
解题思路：在飞地的基础上做改动，使用一个栈存储需要改变的节点

class Solution {
    public int[][] move={{0,1},{0,-1},{1,0},{-1,0}};
    public boolean[][] visited;
    public boolean flag;
    public void solve(char[][] board) {
        //多一个栈记录要被改变的区域
        visited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(!visited[i][j]&&board[i][j]=='O'){
                    flag=false;
                    Queue<int[]> needToChange = new LinkedList<>();
                    bfs(board,i,j,needToChange);
                    if(flag==true){
                        needToChange.clear();
                    }else{
                        while(!needToChange.isEmpty()){
                            int[] node=needToChange.poll();
                            board[node[0]][node[1]]='X';
                        }
                    }                        
                }
            }
        }
    }
    public void bfs(char[][] board,int x,int y,Queue<int[]> needToChange){
        if(x==0||x==board.length-1||y==0||y==board[0].length-1){
            flag=true;
        }
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{x,y});
        needToChange.offer(new int[]{x,y});
        visited[x][y]=true;
        while(!queue.isEmpty()){
            int[] node=queue.poll();
            for(int p=0;p<4;p++){
            int nextx=node[0]+move[p][0];
            int nexty=node[1]+move[p][1];
            if(nextx<0||nextx>=board.length||nexty<0||nexty>=board[0].length){
                continue;
            }
            if(!visited[nextx][nexty]&&board[nextx][nexty]=='O'){
                if(nextx==0||nextx==board.length-1||nexty==0||nexty==board[0].length-1)       {
                    flag=true;
                }
                queue.offer(new int[]{nextx,nexty});
                needToChange.offer(new int[]{nextx,nexty});
                visited[nextx][nexty]=true;
            }
            }
        }
    }
}
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

417. 太平洋大西洋水流问题

题目：有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
题目链接：417. 太平洋大西洋水流问题
**解题思路：**找到哪些点 可以同时到达太平洋和大西洋。 流动的方式只能从高往低流。从太平洋边上的节点 逆流而上，将遍历过的节点都标记上。 从大西洋的边上节点 逆流而长，将遍历过的节点也标记上。 然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
代码如下：

class Solution {
    private static final int[][] position = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    /**
     * 循环遍历超时时可以将需要遍历搜索的点加入队列再进行遍历搜索
     */
    public void bfs(int[][] heights, Queue<int[]> queue, boolean[][][] visited) {
        while (!queue.isEmpty()) {
            int[] curPos = queue.poll();
            for (int[] current: position) {
                int row = curPos[0] + current[0], col = curPos[1] + current[1], sign = curPos[2];
                // 越界
                if (row < 0 || row >= heights.length || col < 0 || col >= heights[0].length) continue;
                // 高度不合适或者已经被访问过了
                if (heights[row][col] < heights[curPos[0]][curPos[1]] || visited[row][col][sign]) continue;
                visited[row][col][sign] = true;
                queue.add(new int[]{row, col, sign});
            }
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int rowSize = heights.length, colSize = heights[0].length;
        List<List<Integer>> ans = new ArrayList<>();
        boolean[][][] visited = new boolean[rowSize][colSize][2];
        // 队列，保存的数据为 [行号, 列号, 标记]
        // 假设太平洋的标记为 1，大西洋为 0
        Queue<int[]> queue = new ArrayDeque<>();
        for (int row = 0; row < rowSize; row++) {
            visited[row][colSize - 1][0] = true;
            visited[row][0][1] = true;
            queue.add(new int[]{row, colSize - 1, 0});
            queue.add(new int[]{row, 0, 1});
        }
        for (int col = 0; col < colSize; col++) {
            visited[rowSize - 1][col][0] = true;
            visited[0][col][1] = true;
            queue.add(new int[]{rowSize - 1, col, 0});
            queue.add(new int[]{0, col, 1});
        }
        bfs(heights, queue, visited);
        for (int row = 0; row < rowSize; row++) {
            for (int col = 0; col < colSize; col++) {
                // 如果该位置即可以到太平洋又可以到大西洋，就放入答案数组
                if (visited[row][col][0] && visited[row][col][1])
                    ans.add(List.of(row, col));
            }
        }
        return ans;
    }
        
}
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