题目描述
这是 LeetCode 上的 1034. 边界着色 ，难度为 中等。
Tag : 「图论 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.lengthm==grid.length
- n == grid[i].lengthn==grid[i].length
- 1 <= m, n <= 501<=m,n<=50
- 1 <= grid[i][j], color <= 10001<=grid[i][j],color<=1000
- 0 <= row < m0<=row<m
- 0 <= col < n0<=col<n
基本分析
这是一道结合「阅读理解」的常规图论搜索题。
基本题意为：从题目给定的 (row, col)(row,col) 进行出发，如果遍历到「连通分量的边界」格子，则使用 colorcolor 进行上色。
同一「连通分量」的「非边界」格子满足：当前格子的四联通方向均存在相邻格子，且当前格子与四联通相邻格子颜色一致。
也就是说，我们从 (row, col)(row,col) 进行出发，遍历 (row, col)(row,col) 所在的「连通分量」，如果遍历到的「连通分量」格子不满足上述条件（边界格子），则进行上色。
BFS
具体的，我们可以使用 BFS 进行求解：
- 构造 ansans 矩阵作为答案，同时 ansans 也作为判重数组使用（通过判断 ans[i][j]ans[i][j] 是否为 00 来得知是否被处理）；
- 起始时，将(row, col)(row,col)位置进行入队，每次从队列中取出元素进行「四联通拓展」：
- 拓展格子必须与起点格子处于同一「连通分量」，即满足两者起始颜色相同；
- 进行「四联通拓展」的同时，记录当前出队是否为边界格子。若为边界格子，则使用 colorcolor 进行上色；
- 跑完
BFS后，对 ansans 进行遍历，将未上色（ans[i][j] = 0ans[i][j]=0）的位置使用原始色（grid[i][j]grid[i][j]）进行上色。
代码：
class Solution { public int[][] colorBorder(int[][] grid, int row, int col, int color) { int m = grid.length, n = grid[0].length; int[][] ans = new int[m][n]; int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}}; Deque<int[]> d = new ArrayDeque<>(); d.addLast(new int[]{row, col}); while (!d.isEmpty()) { int[] poll = d.pollFirst(); int x = poll[0], y = poll[1], cnt = 0; for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (grid[x][y] != grid[nx][ny]) continue; else cnt++; if (ans[nx][ny] != 0) continue; d.addLast(new int[]{nx, ny}); } ans[x][y] = cnt == 4 ? grid[x][y] : color; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (ans[i][j] == 0) ans[i][j] = grid[i][j]; } } return ans; } } 复制代码
- 时间复杂度：O(m * n)O(m∗n)
- 空间复杂度：O(m * n)O(m∗n)
DFS
同理，可以使用 DFS 进行求解。
由于使用 DFS 搜索时，我们使用「栈帧压栈/弹栈」作为拓展联通节点的容器，且仅在出队时进行上色。为防止「重复入队」问题，我们需要先在对节点 (nx, ny)(nx,ny) 入队时，先设置将 ans[nx][ny]ans[nx][ny] 设置为 -1−1 标识位，以作为判重依据。
代码：
class Solution { int m, n, c; int[][] grid, ans; int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}}; public int[][] colorBorder(int[][] _grid, int row, int col, int color) { grid = _grid; c = color; m = grid.length; n = grid[0].length; ans = new int[m][n]; dfs(row, col); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (ans[i][j] == 0) ans[i][j] = grid[i][j]; } } return ans; } void dfs(int x, int y) { int cnt = 0; for (int[] di : dirs) { int nx = x + di[0], ny = y + di[1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; if (grid[x][y] != grid[nx][ny]) continue; else cnt++; if (ans[nx][ny] == -1) continue; ans[nx][ny] = -1; dfs(nx, ny); } ans[x][y] = cnt == 4 ? grid[x][y] : c; } } 复制代码
- 时间复杂度：O(m * n)O(m∗n)
- 空间复杂度：O(m * n)O(m∗n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1034 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
