一、Problem

给出一个二维整数网格 grid，网格中的每个值表示该位置处的网格块的颜色。

只有当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一连通分量。

连通分量的边界是指连通分量中的所有与不在分量中的正方形相邻（四个方向上）的所有正方形，或者在网格的边界上（第一行/列或最后一行/列）的所有正方形。

给出位于 (r0, c0) 的网格块和颜色 color，使用指定颜色 color 为所给网格块的连通分量的边界进行着色，并返回最终的网格 grid

示例 1：
输入：grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
输出：[[3, 3], [3, 2]]示例 2：
输入：grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
输出：[[1, 3, 3], [2, 3, 3]]示例 3：
输入：grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
输出：[[2, 2, 2], [2, 1, 2], [2, 2, 2]]

提示：

1 <= grid.length <= 50
1 <= grid[0].length <= 50
1 <= grid[i][j] <= 1000
0 <= r0 < grid.length
0 <= c0 < grid[0].length
1 <= color <= 1000

二、Solution

方法一：dfs

需要染色的格子：

• 颜色为初始颜色 c 的且和初始位置的格子 (r0, c0) 在一个连通块的方块，但这样的方块也分为两种：
  • 在边界上的
  • 不在边界，但四周至少有一个颜色不一样的方块

所以你会看到示例 2 的初始方块被染色了，而示例 3 的初始方块没有被染色，愿意就是实例 2 的初始方块在边界上，而示例 3 的初始方块周围一个颜色不相同的方块都没有，但相同颜色的方块都在边界上。

总之这题真的气人…

class Solution {int n, m, g[][];boolean vis[][], a[][];final static int[][] ds = { {1,0},{0,-1},{0,1},{-1,0} };boolean need(int x, int y) {for (int[] d : ds) {int tx = x + d[0], ty = y + d[1];if (g[tx][ty] != g[x][y])return true;}return false;}void dfs(int x, int y) { //能到这里的都是一个连通块的格子（即颜色一样），那么此时要染色的情况有二：// 在边界上的连通块// 四周有一个颜色不同if (x == 0 || y == 0 || x == n-1 || y == m-1 || need(x, y)) a[x][y] = true;for (int[] d : ds) {int tx = x + d[0], ty = y + d[1];if (tx < 0 || ty < 0 || tx >= n || ty >= m || vis[tx][ty] || g[tx][ty] != g[x][y])  // continue;vis[tx][ty] = true;dfs(tx, ty);}}public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {g = grid;n = g.length; m = g[0].length;a = new boolean[n][m];vis = new boolean[n][m];vis[r0][c0] = true;dfs(r0, c0);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) if (a[i][j])g[i][j] = color;return g;}
}

复杂度分析

• 时间复杂度：$O(R × C)$，
• 空间复杂度：$O(R × C)$，