[数据结构与算法]1034. 边界着色-深度优先遍历

1034. 边界着色

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

两个网格块属于同一 连通分量 需满足下述全部条件：

两个网格块颜色相同
在上、下、左、右任意一个方向上相邻

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：

在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
在网格的边界上（第一行/列或最后一行/列）

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。

示例 1：

输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出：[[3,3],[3,2]]

示例 2：

输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出：[[1,3,3],[2,3,3]]

示例 3：

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
输出：[[2,2,2],[2,1,2],[2,2,2]]

个人觉得这个题目还是很棒的，感兴趣的，可以多了解一下，这个算法跟联通分量和区域边界有关，很好的一个题目，掌握了可以解决很多问题，解题代码如下：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

 void dfs(int **grid,int n,int m,int x_now,int y_now,int val,int to_val,int **r){
     int direction[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    int pr=0;
      for(int i=0;i<4;i++){ 
          int x_next=x_now+direction[i][0];
         int y_next=y_now+direction[i][1];
         if(x_next>=0&&x_next<n&&y_next>=0&&y_next<m){
         //    printf("%d %d ",x_next,y_next);
             if(grid[x_next][y_next]!=val&&r[x_next][y_next]==0){
                 pr=1;
                  break;
                

             }
         }
         else{
             pr=1;
             break;
         }

      }
      if(pr==1){
          grid[x_now][y_now]=to_val;

      }
     for(int i=0;i<4;i++){
         int x_next=x_now+direction[i][0];
         int y_next=y_now+direction[i][1];
         if(x_next>=0&&x_next<n&&y_next>=0&&y_next<m){
        //     printf("%d %d ",x_next,y_next);
             if(grid[x_next][y_next]==val&&r[x_next][y_next]==0){
                 
                 r[x_next][y_next]=1;
                 dfs(grid,n,m,x_next,y_next,val,to_val,r);

             }
         }
     }

 }
int** colorBorder(int** grid, int gridSize, int* gridColSize, int row, int col, int color, int* returnSize, int** returnColumnSizes){
    int n=gridSize,m=gridColSize[0];
    int **r=(int **)malloc(sizeof(int *)*n);
    * returnColumnSizes=(int *)malloc(sizeof(int )*n);
     *returnSize=n;
    for(int i=0;i<n;i++){
        (* returnColumnSizes)[i]=m;
        r[i]=(int *)malloc(sizeof(int )*m);
        for(int j=0;j<m;j++){
            r[i][j]=0;
        }
    }
 //   printf("dsdaf");
     r[row][col]=1;
   dfs(grid,n,m,row,col,grid[row][col],color,r);
  

return grid;
}