1034. Coloring A Border

1. Question

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 belong to the same connected component if they have the same color and are next to each other in any of the 4 directions.

The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to 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.

2. Examples

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]]

3. Constraints

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

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/coloring-a-border 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

class Solution {

  // 模拟四个方位的坐标
  final int[] dx = {0, 0, 1, -1};
  final int[] dy = {-1, 1, 0, 0};

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

  private void dfs(int[][] grid, int row, int col, int color, boolean[][] visited) {
    int count = 0;
    visited[row][col] = true;

    for(int i = 0; i < 4; i++) {
      int x = row + dx[i];
      int y = col + dy[i];

      // 在边界内
      if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length) {
        // 值相等 未访问过
        if(grid[x][y] == grid[row][col] && !visited[x][y]) {
          dfs(grid, x, y, color, visited);
        }

        if (visited[x][y]) {
          count++;
        }
      }
    }

    if (count != 4) {
      grid[row][col] = color;
    }
  }

}