題目鏈接
難度：中等 ??????類型： 數(shù)組、深度優(yōu)先搜索
給出一個(gè)二維整數(shù)網(wǎng)格 grid，網(wǎng)格中的每個(gè)值表示該位置處的網(wǎng)格塊的顏色。
只有當(dāng)兩個(gè)網(wǎng)格塊的顏色相同，而且在四個(gè)方向中任意一個(gè)方向上相鄰時(shí)，它們屬于同一連通分量。
連通分量的邊界是指連通分量中的所有與不在分量中的正方形相鄰（四個(gè)方向上）的所有正方形，或者在網(wǎng)格的邊界上（第一行/列或最后一行/列）的所有正方形。
給出位于 (r0, c0) 的網(wǎng)格塊和顏色 color，使用指定顏色 color 為所給網(wǎng)格塊的連通分量的邊界進(jìn)行著色，并返回最終的網(wǎng)格 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]]
解題思路
只要四個(gè)邊不全，就上色
代碼實(shí)現(xiàn)
class Solution(object):
def colorBorder(self, grid, r0, c0, color):
"""
:type grid: List[List[int]]
:type r0: int
:type c0: int
:type color: int
:rtype: List[List[int]]
"""
old_color = grid[r0][c0]
new_color = color
n, m = len(grid), len(grid[0])
seen = set()
def dfs(i,j):
if (i,j) in seen: return True
if not (0<=i<n and 0<=j<m and grid[i][j] == old_color):
return False
seen.add((i,j))
if dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)<4:
grid[i][j] = new_color
return True
dfs(r0, c0)
return grid
