【LeetCode练习】[中等]1034.边框着色

【LeetCode练习】[中等]1034. 边框着色

题目来源
算法思想&＃xff1a;二维数组

题目&＃xff1a;

思路:

1. 首先寻找连通部分, 标记遍历过的格子;
2. 在找连通部分中, 判断当前格子是否是边界, 如果是边界, 进行着色;
3. 采用深度优先遍历方法

java代码

class Solution {private int num;//记录grid[r0][c0]的值private int row;//行数private int col;//列数private boolean[][] flag;//用来标记grid[i]][j]是否被访问过public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {row &＃61; grid.length;col &＃61; grid[0].length;num &＃61; grid[r0][c0];if(num &＃61;&＃61; color){//如果更新颜色与原来的相同,直接返回return grid;}flag &＃61; new boolean[row][col];//初始化标记数组dfsFill(grid, r0, c0, color);//递归,深度遍历return grid;}private void dfsFill(int[][] grid, int i, int j, int color) {//判断,i,j是否越界, 以及是否是连通分量的一部分,该坐标是否被访问过, if (i > -1 && i < row && j > -1 && j < col && grid[i][j] &＃61;&＃61; num && !flag[i][j]) {//如果是边界,将其着色if (i &＃61;&＃61; 0 || i &＃61;&＃61; row-1 || //第一行或者最后一行j &＃61;&＃61; 0 || j &＃61;&＃61; col-1 || //第一列或者最后一列(!flag[i-1][j] && grid[i-1][j] !&＃61; num) || //上边没有被访问过,且不属于连通分量(!flag[i&＃43;1][j] && grid[i&＃43;1][j] !&＃61; num) || //下边没有被访问过,且不属于连通分量(!flag[i][j-1] && grid[i][j-1] !&＃61; num) || //左边没有被访问过,且不属于连通分量(!flag[i][j&＃43;1] && grid[i][j&＃43;1] !&＃61; num)) {//右边没有被访问过,且不属于连通分量grid[i][j] &＃61; color;//着色}flag[i][j] &＃61; true;//将遍历过的设置成访问过//递归上下左右进行颜色的修改dfsFill(grid, i-1, j, color);//上方dfsFill(grid, i&＃43;1, j, color);//下方dfsFill(grid, i, j-1, color);//左边dfsFill(grid, i, j&＃43;1, color);//右边}}
}