1034.边界着色

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row 、 col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一 连通分量 。
连通分量的边界 是指连通分量中的所有与不在分量中的网格块相邻（四个方向上）的所有网格块，或者在网格的边界上（第一行/列或最后一行/列）的所有网格块。
请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。
示例 1：

输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出：[[3,3],[3,2]]

示例 2：

输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出：[[1,3,3],[2,3,3]]

示例 3：

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
输出：[[2,2,2],[2,1,2],[2,2,2]]

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j], color <= 1000
• 0 <= row < m
• 0 <= col < n

解法一：三色法

这个方法是由于知道起点才这么做的。

var pairs = []struct{ x, y int }{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
    getColor := grid[row][col]

    dfs(grid, row, col, color, getColor)
    for i, row := range grid {
        for j, val := range row {
            if val == -1 {
                grid[i][j] = color
            } else if val == 0 {
                grid[i][j] = getColor
            }
        }
    }
    return grid
}

func dfs(grid [][]int, x, y, setColor, getColor int) bool {
    if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) {
        return true
    }
    if grid[x][y] < 1 {
        return false
    }
    if grid[x][y] != getColor {
        return true
    }
    grid[x][y] = 0
    for _, pair := range pairs {
        if dfs(grid, x+pair.x, y+pair.y, setColor, getColor) {
            grid[x][y] = -1
        }
    }
    return false
}

解法二：DFS

var pairs = []struct{ x, y int }{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
    m := len(grid)
    n := len(grid[0])
    visited := make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    getColor := grid[row][col]

    var dfs func(x, y int) bool

    dfs = func(x, y int) bool {
        if x < 0 || y < 0 || x >= m || y >= n {
            return true
        }
        if visited[x][y] {
            return false
        }
        if grid[x][y] != getColor {
            return true
        }
        visited[x][y] = true
        for _, pair := range pairs {
            if dfs(x+pair.x, y+pair.y) {
                grid[x][y] = color
            }
        }
        return false
    }
    dfs(row, col)
    return grid
}