1034.边界着色

原题

找连通分量:从(row,col)开始dfs遍历矩阵,记颜色为colorOld,递归访问其上下左右;注意当且仅当某个位置(i,j)颜色也是colorOld才进入递归。当dfs结束,访问过的全部位置就是连通分量

找边界有两种:一是矩阵边界,二是连通分量边界(可通过看上下左右是否有其他颜色判断)

class Solution:
    def colorBorder(self, grid, row: int, col: int, color: int) :
        rec = []
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]	#防止重复访问
        colorOld = grid[row][col]
        #dfs遍历函数
        def dfs(i, j):
            if i < 0 or i > m-1 or j < 0 or j > n-1 or visited[i][j]:	#递归出口
                return
            visited[i][j] = True
            if  grid[i][j] == colorOld:
                # 1、矩阵边界
                # 2、连通分量边界(上下左右有颜色不同的)
                if i ==0 or i == m-1 or j == 0 or j == n-1 \
                        or grid[i-1][j] != colorOld \
                        or grid[i+1][j] != colorOld \
                        or grid[i][j-1] != colorOld \
                        or grid[i][j+1] != colorOld:
                    rec.append((i, j))  #记录位置
                # 递归访问上下左右
                dfs(i - 1, j)
                dfs(i + 1, j)
                dfs(i, j - 1)
                dfs(i, j + 1)
	    #从(row,col)开始
        dfs(row, col)
        #将所有记录的位置着色
        for i, j in rec:
            grid[i][j] = color
        return grid

最后更新于