subject

Source: LeetCode https://leetcode-cn.com/problems/coloring-a-border/

Give you an integer matrix grid of size m x n, representing a grid. I'll give you three integers, row, col and color. Each value in the grid represents the color of the grid block at that location. Two grid blocks belong to the same connected component, and all the following conditions need to be met:

• The two grid blocks are the same color
• Adjacent in any direction of up, down, left and right

The boundary of the connected component refers to all grid blocks in the connected component that meet one of the following conditions:

• It is adjacent to grid blocks that do not belong to the same connected component in the up, down, left and right directions
• On the boundary of the grid (first row / column or last row / column)

Please use the specified color to color the boundaries of all connected components containing grid block grid[row][col], and 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]]

Tips:

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

solution

• The conventional idea is to use depth first search or breadth first search to find the connected component of the position (row,col). The additional thing to do is to judge whether the current point belongs to the boundary. If it belongs to a boundary, you need to add the point to an array used to store all boundary points. When the search is completed, all boundary points are shaded.
• The depth first search is realized by recursion, and the connected components are traversed. A matrix visited with the same size as grid is used to record whether the current node has been accessed, and the boundary points are stored in the array borders
• python

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        borders = []
        originalColor = grid[row][col]
        visited[row][col] = True
        self.dfs(grid, row, col, visited, borders, originalColor)
        for x, y in borders:
            grid[x][y] = color
        return grid

    def dfs(self, grid, x, y, visited, borders, originalColor):  
        isBorder = False        
        m, n = len(grid), len(grid[0])
        direc = ((-1, 0), (1, 0), (0, -1), (0, 1))
        for dx, dy in direc:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == originalColor):
                isBorder = True
            elif not visited[nx][ny]:
                visited[nx][ny] = True
                self.dfs(grid, nx, ny, visited, borders, originalColor)
        if isBorder:
            borders.append((x, y))

• c++

class Solution {
typedef pair<int, int> pii;

class Solution {
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pii> borders;
        int originalColor = grid[row][col];
        visited[row][col] = true;
        dfs(grid, row, col, visited, borders, originalColor);
        for (auto & [x, y] : borders) {
            grid[x][y] = color;
        }
        return grid;
    }

    void dfs(vector<vector<int>>& grid, int x, int y, vector<vector<bool>> & visited, vector<pii> & borders, int originalColor) {
        int m = grid.size(), n = grid[0].size();
        bool isBorder = false;
        int direc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            int nx = direc[i][0] + x, ny = direc[i][1] + y;
            if (!(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == originalColor)) {
                isBorder = true;
            } else if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                dfs(grid, nx, ny, visited, borders, originalColor);
            }                
        }
        if (isBorder) {
            borders.emplace_back(x, y);
        }
    }
};

Complexity analysis

• Time complexity:
  • O(MN)O(mn): where m and n are the number of rows and columns of the grid, respectively. In the worst case, you need to access every point in the grid
• Spatial complexity
  • O(MN) O(mn): use a matrix of the same size as the grid to store whether each point has been traversed. Other space consumption, such as the queue used for breadth first search and the array used to store all boundary points, shall not exceed O(mn)