Question

1034. Coloring A Border

中文文档

Description

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the color of the grid square at that location.

Two squares are called adjacent if they are next to each other in any of the 4 directions.

Two squares belong to the same connected component if they have the same color and they are adjacent.

The border of a connected component is all the squares in the connected component that are either adjacent to (at least) a square not in the component, or on the boundary of the grid (the first or last row or column).

You should color the border of the connected component that contains the square grid[row][col] with color.

Return _the final grid_.

 

Example 1:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

Example 2:

Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

 

Constraints:

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

Solutions

Solution 1

class Solution:
  def colorBorder(
    self, grid: List[List[int]], row: int, col: int, color: int
  ) -> List[List[int]]:
    def dfs(i: int, j: int, c: int) -> None:
      vis[i][j] = True
      for a, b in pairwise((-1, 0, 1, 0, -1)):
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n:
          if not vis[x][y]:
            if grid[x][y] == c:
              dfs(x, y, c)
            else:
              grid[i][j] = color
        else:
          grid[i][j] = color

    m, n = len(grid), len(grid[0])
    vis = [[False] * n for _ in range(m)]
    dfs(row, col, grid[row][col])
    return grid

class Solution {
  private int[][] grid;
  private int color;
  private int m;
  private int n;
  private boolean[][] vis;

  public int[][] colorBorder(int[][] grid, int row, int col, int color) {
    this.grid = grid;
    this.color = color;
    m = grid.length;
    n = grid[0].length;
    vis = new boolean[m][n];
    dfs(row, col, grid[row][col]);
    return grid;
  }

  private void dfs(int i, int j, int c) {
    vis[i][j] = true;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (!vis[x][y]) {
          if (grid[x][y] == c) {
            dfs(x, y, c);
          } else {
            grid[i][j] = color;
          }
        }
      } else {
        grid[i][j] = color;
      }
    }
  }
}

class Solution {
public:
  vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
    int m = grid.size();
    int n = grid[0].size();
    bool vis[m][n];
    memset(vis, false, sizeof(vis));
    int dirs[5] = {-1, 0, 1, 0, -1};
    function<void(int, int, int)> dfs = [&](int i, int j, int c) {
      vis[i][j] = true;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k];
        int y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          if (!vis[x][y]) {
            if (grid[x][y] == c) {
              dfs(x, y, c);
            } else {
              grid[i][j] = color;
            }
          }
        } else {
          grid[i][j] = color;
        }
      }
    };
    dfs(row, col, grid[row][col]);
    return grid;
  }
};

func colorBorder(grid [][]int, row int, col int, color int) [][]int {
  m, n := len(grid), len(grid[0])
  vis := make([][]bool, m)
  for i := range vis {
    vis[i] = make([]bool, n)
  }
  dirs := [5]int{-1, 0, 1, 0, -1}
  var dfs func(int, int, int)
  dfs = func(i, j, c int) {
    vis[i][j] = true
    for k := 0; k < 4; k++ {
      x, y := i+dirs[k], j+dirs[k+1]
      if x >= 0 && x < m && y >= 0 && y < n {
        if !vis[x][y] {
          if grid[x][y] == c {
            dfs(x, y, c)
          } else {
            grid[i][j] = color
          }
        }
      } else {
        grid[i][j] = color
      }
    }
  }
  dfs(row, col, grid[row][col])
  return grid
}

function colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
  const m = grid.length;
  const n = grid[0].length;
  const vis = new Array(m).fill(0).map(() => new Array(n).fill(false));
  const dirs = [-1, 0, 1, 0, -1];
  const dfs = (i: number, j: number, c: number) => {
    vis[i][j] = true;
    for (let k = 0; k < 4; ++k) {
      const x = i + dirs[k];
      const y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        if (!vis[x][y]) {
          if (grid[x][y] == c) {
            dfs(x, y, c);
          } else {
            grid[i][j] = color;
          }
        }
      } else {
        grid[i][j] = color;
      }
    }
  };
  dfs(row, col, grid[row][col]);
  return grid;
}