难度：★★★☆☆
类型：数组
方法：深度优先搜索，宽度优先搜索

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给出一个二维整数网格 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

解答

画图软件读者应该熟悉吧，可以尝试里面的颜料桶操作，把一个连通域换成另一个颜色，但是如果本题仅仅是实现这个功能，就简单了，本题不仅需要找到连通域，而且还要分类联通域中每个点是否属于边界点，仅把边界点进行着色。

我们给出一些定义，把选定点 (r0, c0) 作为起始点，将该点所在联通域作为选定区域，该区域中边界上的点作是着色点。

着色点需要满足以下任意一个条件：
第一，该点在选定区域内，并且该点位于整个方格的边框上；
第二，该点在选定区域内，并且该点周围四个点中，有任意一个点的颜色与该点不同。

一个简单的做法是，我们通过深度优先搜索得到选定区域中的每个点，然后根据上述原则选出来选定区域中的边界点，并对其进行着色。

class Solution:
    def colorBorder(self, grid, r0, c0, color):
        self.grid = [[c for c in row] for row in grid]
        self.rows = len(grid)
        self.columns = len(grid[0])
        self.area = [[False for _ in range(self.columns)] for _ in range(self.rows)]
        self.prev_color = grid[r0][c0]
        self.new_color = color

        def is_border(r, c):
            if r == 0 or r == self.rows - 1:
                return True
            if c == 0 or c == self.columns - 1:
                return True
            return not all(grid[r][c] == grid[nr][nc] for nr, nc in get_neighbors(r, c))

        def get_neighbors(r, c):
            for nr, nc in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
                if 0 <= nr < self.rows and 0 <= nc < self.columns:
                    yield nr, nc

        def dfs(r, c):
            if not self.area[r][c] and self.grid[r][c] == self.prev_color:
                self.area[r][c] = True
                for nr, nc in get_neighbors(r, c):
                    dfs(nr, nc)

        def color_grid():
            for r in range(self.rows):
                for c in range(self.columns):
                    if self.area[r][c] and is_border(r, c):
                        self.grid[r][c] = self.new_color

        dfs(r0, c0)
        color_grid()
        return self.grid


s = Solution()
grid = [[1,2,2],
        [2,3,2]]
print(s.colorBorder(grid, 0, 1, 3))

grid = [[1,1,1],
        [1,1,1],
        [1,1,1]]
print(s.colorBorder(grid, 1, 1, 2))

为了便于理解，以上代码都写成了函数块的方式，当然，可以在代码上做一些简化，尤其要注意逻辑上的判断条件：

from typing import List
class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        if not grid:
            return []
        pos = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        m, n = len(grid), len(grid[0])
        visited = {(r0, c0)}
        target = grid[r0][c0]

        def dfs(r, c):
            for dr, dc in pos:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    if (nr, nc) not in visited:
                        if grid[nr][nc] == target:
                            visited.add((nr, nc))
                            dfs(nr, nc)
                        else:
                            grid[r][c] = color
                else:
                    grid[r][c] = color

        dfs(r0, c0)
        return grid

或者使用宽度优先搜索算法实现，算法流程和上面是一样的，仅仅把递归换成了队列：

from typing import List
class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        if not grid:
            return []
        pos = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        rows, columns = len(grid), len(grid[0])
        queue = [(r0, c0)]
        visited = {(r0, c0)}
        target = grid[r0][c0]

        while queue:
            r, c = queue.pop(0)
            for dr, dc in pos:
                nr = r + dr
                nc = c + dc
                if 0 <= nr < rows and 0 <= nc < columns:
                    if (nr, nc) not in visited:
                        if grid[nr][nc] == target:
                            visited.add((nr, nc))
                            queue.append((nr, nc))
                        else:
                            grid[r][c] = color
                else:
                    grid[r][c] = color

        return grid

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析