1034. 边界着色(BFS+DFS)

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

示例 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:

 1 class Solution {
 2 public:
 3     bool isInArea(int x, int y) {
 4         return (x >= 0 && x < m && y >= 0 && y < n);
 5     }
 6     void bfs(const vectorint>> &grid, int x, int y, vectorbool>> &visited) {
 7         queueint, int>> q;
 8         q.push(make_pair(x, y));
 9         visited[x][y] = true;
10         while (!q.empty()) {
11             bool isBorder = false; // 标记是否为连通分量的边界
12             int curX = q.front().first;
13             int curY = q.front().second;
14             q.pop();
15             for (auto &direction : g_direction) {
16                 int nextX = curX + direction[0];
17                 int nextY = curY + direction[1];
18                 if (!isInArea(nextX, nextY) || grid[nextX][nextY] != originalColor) {
19                     isBorder = true;
20                 } else if (!visited[nextX][nextY]) {
21                     q.push(make_pair(nextX, nextY));
22                     visited[nextX][nextY] = true;
23                 }
24             }
25             if (isBorder) {
26                 borderList.push_back(make_pair(curX, curY));
27             }
28         }
29         return;
30     }
31     vectorint>> colorBorder(vectorint>>& grid, int row, int col, int color) {
32         m = grid.size();
33         n = grid[0].size();
34         vectorbool>> visited(m, vector<bool>(n, false)); // 标记是否被访问
35         originalColor = grid[row][col];
36         visited[row][col] = true;
37         bfs(grid, row, col, visited);
38         // 给网格连通分量的边界进行着色
39         for (auto &pair : borderList) {
40             grid[pair.first][pair.second] = color;
41         }
42         return grid;
43     }
44 private:
45     int m;
46     int n;
47     int originalColor; // 存储给定输入坐标的颜色
48     vectorint, int>> borderList; // 存储边界-需要着色的点
49     vectorint>> g_direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上、右、下、左四个方向
50 };

DFS:

 1 class Solution {
 2 public:
 3     bool isInArea(int x, int y) {
 4         return (x >= 0 && x < m && y >= 0 && y < n);
 5     }
 6     void dfs(const vectorint>> &grid, int x, int y, vectorbool>> &visited) {
 7         bool isBorder = false; // 标记是否为连通分量的边界
 8         for (auto &direction : g_direction) {
 9             int nextX = x + direction[0];
10             int nextY = y + direction[1];
11             /* 连通分量的边界满足如下任意一个条件:
12             * 1、在网格边界上;
13             * 2、在上、下、左、右任意一个方向上与不属于同一连通分量(相邻颜色与当前方格相同)的网格块相邻
14             */
15             if (!isInArea(nextX, nextY) || grid[nextX][nextY] != originalColor) {
16                 isBorder = true;
17             } else if (!visited[nextX][nextY]) {
18                 visited[nextX][nextY] = true;
19                 dfs(grid, nextX, nextY, visited);
20             }
21         }
22         if (isBorder) {
23             borderList.push_back(make_pair(x, y));
24         }
25         return;
26     }
27     vectorint>> colorBorder(vectorint>>& grid, int row, int col, int color) {
28         m = grid.size();
29         n = grid[0].size();
30         vectorbool>> visited(m, vector<bool>(n, false)); // 标记是否被访问
31         originalColor = grid[row][col];
32         visited[row][col] = true;
33         dfs(grid, row, col, visited);
34         // 给网格连通分量的边界进行着色
35         for (auto &pair : borderList) {
36             grid[pair.first][pair.second] = color;
37         }
38         return grid;
39     }
40 private:
41     int m;
42     int n;
43     int originalColor; // 存储给定输入坐标的颜色
44     vectorint, int>> borderList; // 存储边界-需要着色的点
45     vectorint>> g_direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上、右、下、左四个方向
46 };