LeetCode 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]]method: BFS
如果直接在原grid上修改，后面做判断grid[tx][ty] != grid[x][y]的时候会出错，所以另外再开个数组res存结果，同时也可以作为used数组使用，因为遍历过的位置会被赋一个非0的值
只要4个方向上的值与grid[x][y]相同就应该cnt++，而要不要入队除了看值是否相同外还要看是否已经如果队了
const int next[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> res(m, vector<int>(n));
queue<pair<int, int>> q;
q.push({row, col});
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
int cnt = 0;
for (int k = 0; k < 4; k++) {
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx < 0 || tx >= m || ty < 0 || ty >= n) continue;
if (grid[tx][ty] != grid[x][y]) continue; // 值不同就不用看了
else cnt++;
if (res[tx][ty] == 0) q.push({tx, ty}); // 肯定是值相同的
}
res[x][y] = cnt < 4 ? color : grid[x][y];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (res[i][j] == 0) res[i][j] = grid[i][j];
}
}
return res;
}
