力扣连通图问题详解
1.主要思路
采用深度优先遍历，以该点为中心，按照顺时针或者逆时针的方式，遍历其上下左右节点，同时辅以标记数组，遍历过的要做以标记
2.例题
1.图像渲染
class Solution {
int[][] image;
int target;
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
this.image=image;
this.target=image[sr][sc];
if(this.target==color){
return this.image;
}
dfs(sr,sc,color);
return this.image;
}
public void dfs(int sr,int sc,int color){
if(sr<0||sr>=image.length||sc<0||sc>=image[0].length){
return;
}
if(image[sr][sc]!=target){
return;
}
image[sr][sc]=color;
dfs(sr+1,sc,color);
dfs(sr,sc-1,color);
dfs(sr-1,sc,color);
dfs(sr,sc+1,color);
}
}
2.边界着色
class Solution {
int[][] grid;
int color;
int curColor;
boolean[][] used;
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
this.grid=grid;
this.used=new boolean[this.grid.length][this.grid[0].length];
this.color=color;
this.curColor=grid[row][col];
if(this.color==this.curColor){
return this.grid;
}
dfs(row,col);
return this.grid;
}
public void dfs(int row,int col){
if(row<0||col<0||row>=grid.length||col>=grid[0].length){
return;
}
if(used[row][col]||grid[row][col]!=this.curColor){
return;
}
if(row==0||col==0||row==grid.length-1||col==grid[0].length-1){
grid[row][col]=color;
}else if(test(row,col)){
grid[row][col]=color;
}
used[row][col]=true;
dfs(row+1,col);
dfs(row,col-1);
dfs(row-1,col);
dfs(row,col+1);
}
public boolean test(int row,int col){
if(grid[row+1][col]!=curColor&&!used[row+1][col]){
return true;
}
if(grid[row][col+1]!=curColor&&!used[row][col+1]){
return true;
}
if(grid[row-1][col]!=curColor&&!used[row-1][col]){
return true;
}
if(grid[row][col-1]!=curColor&&!used[row][col-1]){
return true;
}
return false;
}
}
3.岛屿数量
class Solution {
boolean[][] used;
char[][] grid;
public int numIslands(char[][] grid) {
this.grid=grid;
this.used=new boolean[this.grid.length][this.grid[0].length];
int count=0;
for (int i = 0; i < this.grid.length; i++) {
for (int j = 0; j < this.grid[0].length; j++) {
if(!this.used[i][j]&&this.grid[i][j]=='1'){
count++;
dfs(i,j);
}
}
}
return count;
}
public void dfs(int x,int y){
if(x<0||y<0||x>=this.grid.length||y>=this.grid[0].length){
return;
}
if(this.grid[x][y]=='0'||this.used[x][y]){
return;
}
this.used[x][y]=true;
dfs(x+1,y);
dfs(x,y-1);
dfs(x-1,y);
dfs(x,y+1);
}
}
4.飞地的数量
class Solution {
boolean flag;
boolean[][] used;
int[][] grid;
public int numEnclaves(int[][] grid) {
this.grid=grid;
this.used=new boolean[grid.length][grid[0].length];
int count=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(this.grid[i][j]==1&&!used[i][j]){
flag=true;
int r=dfs(i,j);
if(flag){
count+=r;
}
}
}
}
return count;
}
public int dfs(int x,int y){
if(x<0||y<0||x>=grid.length||y>=grid[0].length){
return 0;
}
if(grid[x][y]==0||used[x][y]){
return 0;
}
if(x==0||y==0||x== grid.length-1||y== grid[0].length-1){
flag=false;
}
used[x][y]=true;
int i1=dfs(x+1,y);
int i2=dfs(x,y-1);
int i3=dfs(x-1,y);
int i4=dfs(x,y+1);
if(flag){
return i1+i2+i3+i4+1;
}else{
return 0;
}
}
}
5.统计封闭岛屿的数目
class Solution {
boolean flag;
boolean[][] used;
int[][] grid;
public int closedIsland(int[][] grid) {
this.grid=grid;
this.used=new boolean[grid.length][grid[0].length];
int count=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(this.grid[i][j]==0&&!used[i][j]){
flag=true;
dfs(i,j);
if(flag){
count++;
}
}
}
}
return count;
}
public void dfs(int x,int y){
if(x<0||y<0||x>=grid.length||y>=grid[0].length){
return;
}
if(grid[x][y]==1||used[x][y]){
return;
}
if(x==0||y==0||x== grid.length-1||y== grid[0].length-1){
flag=false;
}
used[x][y]=true;
dfs(x+1,y);
dfs(x,y-1);
dfs(x-1,y);
dfs(x,y+1);
}
}
6.被围绕的区域
class Solution {
char[][] board;
boolean[][] used;
boolean flag;
Set<int[]> set=new HashSet<>();
public void solve(char[][] board) {
this.board=board;
this.used=new boolean[board.length][board[0].length];
for (int i = 0; i < this.board.length; i++) {
for (int j = 0; j < this.board[0].length; j++) {
if(this.board[i][j]=='O'&&!used[i][j]){
flag=true;
dfs(i,j);
if(flag){
for (int[] ints : set) {
this.board[ints[0]][ints[1]]='X';
}
}
set.clear();
}
}
}
}
public void dfs(int x,int y){
if(x<0||y<0||x>=board.length||y>=board[0].length){
return;
}
if(used[x][y]||this.board[x][y]=='X'){
return;
}
if(x==0||y==0||x==board.length-1||y==board[0].length-1){
flag=false;
}
used[x][y]=true;
set.add(new int[]{x,y});
dfs(x+1,y);
dfs(x,y-1);
dfs(x-1,y);
dfs(x,y+1);
}
}
7.统计子岛屿
class Solution {
boolean[][] used1;
boolean[][] used2;
int[][] grid1;
int[][] grid2;
boolean flag;
public int countSubIslands(int[][] grid1, int[][] grid2) {
this.grid1=grid1;
this.used1=new boolean[this.grid1.length][this.grid1[0].length];
for (int i = 0; i < grid1.length; i++) {
for (int j = 0; j < grid1[0].length; j++) {
if(!used1[i][j]&&this.grid1[i][j]==1){
dfs1(i,j);
}
}
}
this.grid2=grid2;
int count=0;
this.used2=new boolean[this.grid2.length][this.grid2[0].length];
for (int i = 0; i < grid2.length; i++) {
for (int j = 0; j < grid2[0].length; j++) {
if(!used2[i][j]&&this.grid2[i][j]==1){
flag=true;
dfs2(i,j);
if(flag){
count++;
}
}
}
}
return count;
}
public void dfs1(int x,int y){
if(x<0||y<0||x>=grid1.length||y>=grid1[0].length){
return;
}
if(used1[x][y]||grid1[x][y]==0){
return;
}
used1[x][y]=true;
dfs1(x+1,y);
dfs1(x,y-1);
dfs1(x-1,y);
dfs1(x,y+1);
}
public void dfs2(int x,int y){
if(x<0||y<0||x>=grid2.length||y>=grid2[0].length){
return;
}
if(used2[x][y]||grid2[x][y]==0){
return;
}
used2[x][y]=true;
if(x< grid1.length&&y<grid1[0].length&&!used1[x][y]){
flag=false;
}
dfs2(x+1,y);
dfs2(x,y-1);
dfs2(x-1,y);
dfs2(x,y+1);
}
}
8.岛屿的最大面积
class Solution {
boolean flag;
boolean[][] used;
int[][] grid;
public int maxAreaOfIsland(int[][] grid) {
this.grid=grid;
this.used=new boolean[grid.length][grid[0].length];
int count=0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(this.grid[i][j]==1&&!used[i][j]){
int r=dfs(i,j);
count=Math.max(count,r);
}
}
}
return count;
}
public int dfs(int x,int y){
if(x<0||y<0||x>=grid.length||y>=grid[0].length){
return 0;
}
if(grid[x][y]==0||used[x][y]){
return 0;
}
used[x][y]=true;
int i1=dfs(x+1,y);
int i2=dfs(x,y-1);
int i3=dfs(x-1,y);
int i4=dfs(x,y+1);
return i1+i2+i3+i4+1;
}
}
9.最大人工岛
这道题比较难
class Solution {
static int[] d = {0, -1, 0, 1, 0};
public int largestIsland(int[][] grid) {
int n = grid.length, res = 0;
int[][] tag = new int[n][n];
Map<Integer, Integer> area = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && tag[i][j] == 0) {
int t = i * n + j + 1;
area.put(t, dfs(grid, i, j, tag, t));
res = Math.max(res, area.get(t));
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
int z = 1;
Set<Integer> connected = new HashSet<Integer>();
for (int k = 0; k < 4; k++) {
int x = i + d[k], y = j + d[k + 1];
if (!valid(n, x, y) || tag[x][y] == 0 || connected.contains(tag[x][y])) {
continue;
}
z += area.get(tag[x][y]);
connected.add(tag[x][y]);
}
res = Math.max(res, z);
}
}
}
return res;
}
public int dfs(int[][] grid, int x, int y, int[][] tag, int t) {
int n = grid.length, res = 1;
tag[x][y] = t;
for (int i = 0; i < 4; i++) {
int x1 = x + d[i], y1 = y + d[i + 1];
if (valid(n, x1, y1) && grid[x1][y1] == 1 && tag[x1][y1] == 0) {
res += dfs(grid, x1, y1, tag, t);
}
}
return res;
}
public boolean valid(int n, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}
原文地址：https://blog.csdn.net/m0_61346425/article/details/142928666
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！