代码随想录图论 第三天 | 130. 被围绕的区域 417. 太平洋大西洋水流问题
一、130. 被围绕的区域
题目链接:https://leetcode.cn/problems/surrounded-regions/
思路:题目要求沾边的不动,只改没沾边的,那么可以先dfs遍历4条边,把沾边的O都改成A。然后直接两层for循环遍历整个数组,把O该成X,把A改成O。文章来源:https://www.toymoban.com/news/detail-725934.html
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/
思路:分别从太平洋和大西洋的边界出发,逆流而上进行分开的标记,只要某个格子即被太平洋标记又被大西洋标记即可收取。文章来源地址https://www.toymoban.com/news/detail-725934.html
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);
}
}
}
到了这里,关于代码随想录图论 第三天 | 130. 被围绕的区域 417. 太平洋大西洋水流问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!