无锡市网站搭建,教学网站模板,网站建设合同按什么交印花税,口碑好的邯郸网站建设提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣130. 被围绕的区域二、力扣417. 太平洋大西洋水流问题三、力扣827. 最大人工岛 前言 一、力扣130. 被围绕的区域
class Solution {boolean[][] flag;i… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣130. 被围绕的区域二、力扣417. 太平洋大西洋水流问题三、力扣827. 最大人工岛 前言 一、力扣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);}}}二、力扣417. 太平洋大西洋水流问题
class Solution {int[][] move {{0,1},{0,-1},{-1,0},{1,0}};boolean[][][] flag;// boolean[][] visited;public ListListInteger pacificAtlantic(int[][] heights) {ListListInteger 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);}}
}三、力扣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;MapInteger,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){SetInteger 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);}}
}
