难度：★★★☆☆
类型：数组
方法：深度优先搜索，宽度优先搜索
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给出一个二维整数网格 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解决方案，请移步力扣中等题解析
网友评论