【LeetCode每日一题】1034. 边界着色【中等】DFS/BFS

给你一个大小为 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

题解： 这个题目稍稍有点难读懂，大致意思就是找到相同颜色的边边，然后给边边换个颜色， 里面颜色不变。 我用了一个BFS的写法，开了好多数组，写得有点丑。

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();
        queue<pair<int, int>> q;
        map<pair<int, int>, bool> fin;
        map<pair<int, int>, bool> vis;
        q.push({row, col});
        vis[{row, col}] = true;
        int initcolor = grid[row][col];
        vector<vector<int>> d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        while(!q.empty()){
            auto now = q.front();
            q.pop();
            int x = now.first;
            int y = now.second;
            //cout<<"x:"<<x<<" y:"<<y<<endl;
            //记一下周围是不是都是相同颜色，是的话不是边边
            int cnt = 0;
            for(int i = 0; i < 4; i++){
                int dx = x + d[i][0];
                int dy = y + d[i][1];
                if(dx >= 0 && dx < m && dy >= 0 && dy < n && grid[dx][dy] == initcolor){
                    cnt++;
                    if(!vis[{dx, dy}]){
                        //cout<<"dx:"<<dx<<" dy:"<<dy<<endl;
                        q.push({dx, dy});
                        vis[{dx, dy}] = true;
                    }
                }
            }
            if(cnt != 4) fin[{x, y}] = true;
        }
        vector<vector<int>> ans(m, vector<int>(n));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(fin[{i, j}]){
                    ans[i][j] = color;
                }
                else{
                    ans[i][j] = grid[i][j];
                }
            }
        }
        return ans;
    }
};

附一个DFS的写法

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);
        }
    }
};