力扣-图论-16【算法学习day.66】

2024/12/23 15:52:47 来源：https://blog.csdn.net/2301_79232523/article/details/144568460 浏览: 次关键词：力扣-图论-16【算法学习day.66】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向和记录学习过程（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.统计封闭岛屿的数目

题目链接:1254. 统计封闭岛屿的数目 - 力扣（LeetCode）

题面:

代码:

class Solution {int[][] grid;int[][] flag;int n,m;int ans = 0;int flag2 = 0;public int closedIsland(int[][] grid) {this.grid = grid;n = grid.length;m = grid[0].length;flag = new int[n][m];for(int i = 1;i<n-1;i++){for(int j = 1;j<m-1;j++){if(grid[i][j]==0&&flag[i][j]==0){flag2 = 0;recursion(i,j);if(flag2==0)ans++;}}}return ans;}public void recursion(int x,int y){flag[x][y] = 1;if(x+1<n){if(grid[x+1][y]==0&&flag[x+1][y]==0){recursion(x+1,y);}if(grid[x+1][y]==0&&x+1==n-1)flag2 = 1;}if(x-1>=0){if(grid[x-1][y]==0&&flag[x-1][y]==0){recursion(x-1,y);}if(grid[x-1][y]==0&&x-1==0)flag2 = 1;}if(y+1<m){if(grid[x][y+1]==0&&flag[x][y+1]==0){recursion(x,y+1);}if(grid[x][y+1]==0&&y+1==m-1)flag2 = 1;}if(y-1>=0){if(grid[x][y-1]==0&&flag[x][y-1]==0){recursion(x,y-1);}if(grid[x][y-1]==0&&y-1==0)flag2 = 1;}}
}

2.被围绕的区域

题目链接:130. 被围绕的区域 - 力扣（LeetCode）

题面:

分析:这题可以换个思路从边界遍历，然后dfs标记所有和边界中‘O’相连的‘O’

代码:

class Solution {char[][] board;int n,m;int[][] flag;int flag2;public void solve(char[][] board) {this.board = board;n = board.length;m = board[0].length;flag = new int[n][m];for(int i = 0;i<n;i++){if(board[i][0]=='O'&&flag[i][0]==0){recursion(i,0);}if(board[i][m-1]=='O'&&flag[i][m-1]==0){recursion(i,m-1);}}for(int i = 1;i<m-1;i++){if(board[0][i]=='O'&&flag[0][i]==0){recursion(0,i);}if(board[n-1][i]=='O'&&flag[n-1][i]==0){recursion(n-1,i);}}for(int i = 1;i<n-1;i++){for(int j = 1;j<m-1;j++){if(board[i][j]=='O'&&flag[i][j]==0){board[i][j] = 'X';}}}}public void recursion(int x,int y){flag[x][y] = 1;if(x+1<n&&board[x+1][y]=='O'&&flag[x+1][y]==0){recursion(x+1,y);}if(x-1>=0&&board[x-1][y]=='O'&&flag[x-1][y]==0){recursion(x-1,y);}if(y+1<m&&board[x][y+1]=='O'&&flag[x][y+1]==0){recursion(x,y+1);}if(y-1>=0&&board[x][y-1]=='O'&&flag[x][y-1]==0){recursion(x,y-1);}}
}

3.统计子岛屿

题目链接:1905. 统计子岛屿 - 力扣（LeetCode）

题面:

代码:

class Solution {int[][] grid1;int[][] grid2;int n,m;int[][] flag;int flag2 = 0;int ans = 0;public int countSubIslands(int[][] grid1, int[][] grid2) {this.grid1 = grid1;this.grid2 = grid2;n  = grid1.length;m  = grid1[0].length;flag = new int[n][m];for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(grid2[i][j]==1&&flag[i][j]==0){flag2 = 0;recursion(i,j);// System.out.println("_______________________________");if(flag2==0)ans++;}}}return ans;}public void recursion(int x,int y){// System.out.println(x+"                 "+y);if(grid1[x][y]!=grid2[x][y])flag2 = 1;flag[x][y] = 1;if(x+1<n&&grid2[x+1][y]==1&&flag[x+1][y]==0){recursion(x+1,y);}if(x-1>=0&&grid2[x-1][y]==1&&flag[x-1][y]==0){recursion(x-1,y);}if(y+1<m&&grid2[x][y+1]==1&&flag[x][y+1]==0){recursion(x,y+1);}if(y-1>=0&&grid2[x][y-1]==1&&flag[x][y-1]==0){recursion(x,y-1);}}   
}