判断一个矩阵是否在另一个矩阵中满足条件
class Solution {
int res=0;
boolean flag=true;
public int countSubIslands(int[][] grid1, int[][] grid2) {
int n=grid1.length;int m=grid1[0].length;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid2[i][j]==1){
flag=true;
dfs(grid1,grid2,i,j);
if(flag){
res++;
}
}
}
}
return res;
}
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public void dfs(int[][] grid1,int[][] grid2,int i,int j){
if(grid1[i][j]!=1){
flag=false;//如果存在不是1的节点,对应的就不是子矩阵
}
//递归fill-flood还是会将所有的节点都进行染色
grid2[i][j]=0;
for(int k=0;k<4;k++){
int a=i+dx[k];
int b=j+dy[k];
if(a>=0&&a<grid1.length&&b>=0&&b<grid1[0].length&&grid2[a][b]==1){
dfs(grid1,grid2,a,b);
}
}
}
}
矩阵连通块的边界
迷宫中离入口最近的出口
迷宫中离入口最近的出口
对于出口:下一个位置不在矩形范围内的位置为出口,但是对于entrance不能为出口,如果entrances在出口边上,继续下一轮的BFS
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int nearestExit(char[][] maze, int[] entrance) {
int n=maze.length;int m=maze[0].length;
Queue<int[]> queue=new LinkedList<int[]>();
boolean[][] vis=new boolean[n][m];
queue.offer(entrance);
vis[entrance[0]][entrance[1]]=true;
int res=0;
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
int[] node=queue.poll();
for(int k=0;k<4;k++){
int a=node[0]+dx[k];
int b=node[1]+dy[k];
// System.out.println("a"+a+"b"+b);
if(!(a>=0&&a<n&&b>=0&&b<m)){
if(node[0]==entrance[0]&&node[1]==entrance[1]){
continue;
}
return res;
}else if(!vis[a][b]&&maze[a][b]!='+'){
vis[a][b]=true;
queue.offer(new int[]{a,b});
}
}
}
res++;
}
return -1;
}
}
将所有的边界进行染色
边界染色
连通块的边界就是下一个位置越界或者下一个位置与当前连通块的颜色不一样
先将所有的需要进行染色的位置保存
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
//将所有的
List<int[]> pos=new ArrayList<int[]>();
public int[][] colorBorder(int[][] grid, int row, int col, int color) {
boolean[][] vis=new boolean[grid.length][grid[0].length];
vis[row][col]=true;
dfs(grid,row,col,grid[row][col],vis);
for(int i=0;i<pos.size();i++){
int[] node=pos.get(i);
grid[node[0]][node[1]]=color;
}
return grid;
}
public void dfs(int[][] grid,int i,int j,int original,boolean[][] vis){
for(int k=0;k<4;k++){
int a=i+dx[k];
int b=j+dy[k];
if(!(a>=0&&a<grid.length&&b>=0&&b<grid[0].length&&grid[a][b]==original)){
pos.add(new int[]{i,j});
}else if(!vis[a][b]){
vis[a][b]=true;
dfs(grid,a,b,original,vis);
}
}
}
}
地图中的最高点
地图中的最高点
将节点添加进队列之前将该元素进行标记,能够保证该元素只被扩展一次
class Solution {
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int[][] highestPeak(int[][] isWater) {
int n=isWater.length;
int m=isWater[0].length;
Queue<int[]> queue=new LinkedList<int[]>();
boolean[][] vis=new boolean[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(isWater[i][j]==1){
isWater[i][j]=0;
vis[i][j]=true;
queue.offer(new int[]{i,j,0});
}
}
}
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
int[] node=queue.poll();
for(int k=0;k<4;k++){
int a=node[0]+dx[k];
int b=node[1]+dy[k];
if(a>=0&&a<n&&b>=0&&b<m&&!vis[a][b]){
isWater[a][b]=node[2]+1;
vis[a][b]=true;
queue.offer(new int[]{a,b,isWater[a][b]});
}
}
}
}
return isWater;
}
}