【深度优先搜索-中等】1034. 边界着色

【题目】
注意：这题是对联通分量的边界进行着色，笔者第一遍做的时候就是忽略了这一点

【代码】

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        origin=grid[row][col]
        if origin==color:return grid
        stack=[(row,col)]
        p=set()
        while stack:
            row,col=stack.pop()
            if 0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]==origin:
                p.add((row,col))
                for mx,my in [(row-1,col),(row+1,col),(row,col-1),(row,col+1)]:
                    if (mx,my) not in p:
                        stack.append((mx,my))
        for x,y in p:            
            for row,col in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:
                if (0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]!=origin and (row,col) not in p) or not(0<=row<len(grid) and 0<=col<len(grid[0])):
                    grid[x][y]=color
        return grid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

【方法2】dfs

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        origin=grid[row][col]
        if origin==color:return grid
        def dfs(row,col):
            if 0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]==origin:
                grid[row][col]=99999
                return {(row,col)}|dfs(row-1,col)|dfs(row+1,col)|dfs(row,col-1)|dfs(row,col+1)
            return set()
        p=dfs(row,col)
        for x,y in p:
            for row,col in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:
                if (0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]!=origin and (row,col) not in p) or not(0<=row<len(grid) and 0<=col<len(grid[0])):
                    grid[x][y]=color
                elif (0<=row<len(grid) and 0<=col<len(grid[0]) and grid[row][col]==99999):
                    grid[row][col]=origin
        return grid
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17