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

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

一、130. 被围绕的区域

题目链接：https://leetcode.cn/problems/surrounded-regions/
思路：题目要求沾边的不动，只改没沾边的，那么可以先dfs遍历4条边，把沾边的O都改成A。然后直接两层for循环遍历整个数组，把O该成X，把A改成O。

class Solution {public void solve(char[][] board) {for (int i = 0; i < board.length; i++) {if (board[i][0] == 'O') dfs(board, i, 0);if (board[i][board[0].length-1] == 'O') dfs(board, i, board[0].length-1);}for (int i = 0; i < board[0].length; i++) {if (board[0][i] == 'O') dfs(board, 0, i);if (board[board.length-1][i] == 'O') 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') board[i][j] = 'X';if (board[i][j] == 'A') board[i][j] = 'O';}}}void dfs(char[][] board, int x, int y) {if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != 'O') {return;}board[x][y] = 'A';dfs(board, x-1, y);dfs(board, x+1, y);dfs(board, x, y-1);dfs(board, x, y+1);}
}

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

题目链接：https://leetcode.cn/problems/pacific-atlantic-water-flow/
思路：分别从太平洋和大西洋的边界出发，逆流而上进行分开的标记，只要某个格子即被太平洋标记又被大西洋标记即可收取。

class Solution {boolean[][][] visited;int[][] nums = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public List<List<Integer>> pacificAtlantic(int[][] heights) {List<List<Integer>> arrayLists = new ArrayList<>();visited = new boolean[heights.length][heights[0].length][2];for (int i = 0; i < heights.length; i++) {visited[i][0][0] = true;dfs(heights, i, 0, 0);visited[i][heights[0].length-1][1] = true;dfs(heights, i, heights[0].length-1, 1);}for (int i = 0; i < heights[0].length; i++) {visited[0][i][0] = true;dfs(heights, 0, i, 0);visited[heights.length-1][i][1] = true;dfs(heights, heights.length-1, i,1);}for (int i = 0; i < heights.length; i++) {for (int j = 0; j < heights[0].length; j++) {if (visited[i][j][0] && visited[i][j][1]) {List<Integer> list = new ArrayList<>();list.add(i);list.add(j);arrayLists.add(list);}}}return arrayLists;}void dfs(int[][] heights, int x, int y, int sign) {for (int[] num : nums) {int nX = x + num[0];int nY = y + num[1];if (nX < 0 || nX >= heights.length || nY < 0 || nY >= heights[0].length) {continue;}if (visited[nX][nY][sign] || heights[nX][nY] < heights[x][y]) continue;visited[nX][nY][sign] = true;dfs(heights, nX, nY, sign);}}
}