当前位置: 首页> 健康> 科研 > 1034. 边界着色(JAVA)

1034. 边界着色(JAVA)

时间:2025/7/11 0:52:22来源:https://blog.csdn.net/qq_51791303/article/details/142032994 浏览次数:0次

1034. 边界着色

1.采用BFS或DFS即可。
2.和传统的找联通不一样,本题要求对边界上色,即BFS或DFS均需要保留上一次的坐标,因为判断(x,y)是不是边界需要根据(x±1,y±1)判断,倘若(x±1,y±1)判定"成功",则对(x,y)着色,这就是本题的最大不同。
3.本题我的BFS貌似存在重复上色现象,即有的边界可能被上色多次,故不可以使用取反值进行特殊标记,找到了直接在grid里修改即可。

1.DFS(感觉比BFS容易)

class Solution {public int[][] grid;public boolean[][] vis;public int orginal;public int m,n,color;public int[][] colorBorder(int[][] grid, int row, int col, int color) {m = grid.length;n=grid[0].length;vis= new boolean[m][n];this.grid=grid;this.color=color;orginal=grid[row][col];func(row,col,0,0);return grid;}public void func(int row,int col , int rp , int cp){if((row>=0 && row<m) && (col>=0 && col<n)){if(!vis[row][col]){if(grid[row][col]==orginal){vis[row][col]=true;func(row-1,col,row,col);func(row+1,col,row,col);func(row,col-1,row,col);func(row,col+1,row,col);}else{grid[rp][cp]=color;}}}else{grid[rp][cp]=color;}} 
}

2.BFS

class Solution {public int[][] grid;public boolean[][] vis;public Deque<int[]> q;public int m,n,color,orginal;public int[][] colorBorder(int[][] grid, int row, int col, int color) {m = grid.length;q=new ArrayDeque<>();           //Java 使用ArrayDeque模拟queue,基础操作 isEmpty(),poll()n=grid[0].length;vis= new boolean[m][n];         //布尔数组默认为False;this.grid=grid;this.color=color;orginal=grid[row][col];int[][] dir={{0,-1},{0,1},{1,0},{-1,0}};q.offer(new int[]{row,col});vis[row][col]=true;while(!q.isEmpty()){int[] res=q.poll();int x=res[0],y=res[1];for(int[] i: dir){int nx=x+i[0];int ny=y+i[1];if((0<=nx && nx<m)&& (0<=ny && ny<n)){if(!vis[nx][ny]){            if(grid[nx][ny]==orginal){vis[nx][ny]=true;q.offer(new int[]{nx,ny});}else{grid[x][y]=color;}}}else{grid[x][y]=color;}}}return grid;}}
关键字:1034. 边界着色(JAVA)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: