https://leetcode.com/problems/coloring-a-border/
Given a 2-dimensional
grid of integers, each value in the grid represents the color of the grid square at that location.
Two squares belong to the same connected component if and only if they have the same color and are next to each other in any of the 4 directions.
The border of a connected component is all the squares in the connected component that are either 4-directionally adjacent to a square not in the component, or on the boundary of the grid (the first or last row or column).
Given a square at location
(r0, c0) in the grid and a color, color the border of the connected component of that square with the given color, and return the final grid.
Example 1:
Input: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3 Output: [[3, 3], [3, 2]]
Example 2:
Input: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3 Output: [[1, 3, 3], [2, 3, 3]]
Example 3:
Input: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2 Output: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]
Note:
1 <= grid.length <= 501 <= grid[0].length <= 501 <= grid[i][j] <= 10000 <= r0 < grid.length0 <= c0 < grid[0].length1 <= color <= 1000
https://leetcode.com/problems/coloring-a-border/discuss/283262/Java-BFS-and-DFS-short-codes
- Let m = grid.length, n = grid[0].length, use the number
from 0 to m * n - 1 to identify the cells to avoid duplicates;
e.g., grid[x][y]'s cell number is x * n + y; - put the initial cell [r0, c0] into the Queue then poll it out,
then check if it is on the grid bounday; - Traverse the cell's 4 neighbors:
a) if its neighbor is of different color, the cell is on the
component border;
b) if same color, put the neighbor into Queue; - repeat the above 2 and 3 till Queue is empty.
private static final int[] d = { 0, 1, 0, -1, 0 }; // neighbors' relative displacements.
public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
int clr = grid[r0][c0], m = grid.length, n = grid[0].length;
Set<Integer> seen = new HashSet<>(); // put the cell number into Set to avoid visiting again.
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{ r0, c0 }); // add initial cell.
seen.add(r0 * n + c0); // add initial cell number.
while (!q.isEmpty()) { // BFS starts.
int r = q.peek()[0], c = q.poll()[1];
if (r == 0 || r == m - 1 || c == 0 || c == n - 1) { grid[r][c] = color; } // on grid boundary.
for (int i = 0; i < 4; ++i) { // travers its 4 neighbors.
int x = r + d[i], y = c + d[i + 1]; // neighbor coordinates.
if (x < 0 || x >= m || y < 0 || y >= n || seen.contains(x * n + y)) { continue; } // out of grid or visited already.
if (grid[x][y] == clr) { // its neighbor is of same color.
seen.add(x * n + y); // avoid visiting again.
q.offer(new int[]{ x, y }); // put it into Queue.
}else { // its neighbor is of different color, hence it is on component boundary.
grid[r][c] = color;
}
}
}
return grid;
}
X. DFS
Use DFS to explore the cell (r0, c0)'s component, and negate the visited cell, traverse its 4 neighbors. After the traversal, change back from the negative if the component cell is at inner part.
private int[] d = { 0, 1, 0, -1, 0 }; // neighbors' relative displacements.
public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
dfs(grid, r0, c0, grid[r0][c0]);
for (int[] g : grid) {
for (int i = 0; i < g.length; ++i) {
if (g[i] < 0) { g[i] = color; }
}
}
return grid;
}
private void dfs(int[][] grid, int r, int c, int clr) {
grid[r][c] = -clr; // mark as visited.
int cnt = 0; // use to count grid[r][c]'s component neighbors (same color as itself).
for (int i = 0; i < 4; ++i) { // traverse 4 neighbors.
int x = r + d[i], y = c + d[i + 1]; // nieghbor's coordinates.
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || Math.abs(grid[x][y]) != clr) { continue; } // out of grid or not same component.
++cnt; // only if all 4 neighbors of grid[r][c] have same color as itself, it is on inner part.
if (grid[x][y] == clr) { dfs(grid, x, y, clr); }
}
if (cnt == 4) { grid[r][c] = clr; } // inner part, change back.
}The primary intuition is to do a DFS from the starting cell and find all the cells of the oldColor that needs to be changed. We mark these cells with a negative value of the oldColor. Once this is done, we need to find out which among those cells lies interior and which lies exterior. Interior cells have all 4 neighboring cells(top, bottom, left and right) to have either the oldColor value or -oldColor value. Make these interior cells positive again. Once we have processed this for all necessary nodes from the starting cell, we will get a grid containing negative cells that denote the boundary. We need to sweep through the entire grid and change these negative values to the new color.
- Check for existence of null or empty grid and return null if so.
- Store the color of starting cell grid[r0][c0] in oldColor.
- Initiate a DFS from starting cell.
- Check if the current cell lies out of bounds off the grid or if current cell does not have the same color as starting cell and return if so.
- Otherwise, change the current cell's color to a negative value for us to remember that we have processed this cell.
- Do a DFS for all neighboring points that are up, down, left and right from current cell.
- Once DFS returns back for the current cell after processing all directions from it, change the current cell's color back to positive value if you find that the current cell lies within adjacent cells top, bottom, left and right with the same value.
- Once the entire DFS has been processed, we now have a grid containing negative values representing the border which needs to be recolored to the new color.
class Solution {
public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
if(grid == null || grid.length == 0)
return null;
int oldColor = grid[r0][c0];
dfs(grid, r0, c0, oldColor);
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] < 0)
grid[i][j] = color;
}
}
return grid;
}
public void dfs(int[][] grid, int i, int j, int oldColor) {
if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != oldColor)
return;
grid[i][j] = -oldColor;
dfs(grid, i+1, j, oldColor);
dfs(grid, i-1, j, oldColor);
dfs(grid, i, j+1, oldColor);
dfs(grid, i, j-1, oldColor);
if(i > 0 && j > 0 && i < grid.length-1 && j < grid[0].length-1
&& oldColor == Math.abs(grid[i+1][j])
&& oldColor == Math.abs(grid[i-1][j])
&& oldColor == Math.abs(grid[i][j+1])
&& oldColor == Math.abs(grid[i][j-1]))
grid[i][j] = oldColor;
}https://xingxingpark.com/Leetcode-1034-Coloring-A-Border/
题目给我们一个坐标，要求将这个坐标表示的点所属的
component的边界用给定的颜色标记出来。
我们用
DFS的方法解决这道题。从给定的起点A开始，我们可以方便的遍历A所在的component的所有点。为了不开辟额空间，我们直接将A原来的颜色originColor翻转为-originColor。
那如何在找出边界呢？我们只需要在完成一个点上下左右四个方向的遍历之后，检查这个点是不是在
怎么判断一个方格是否是 The border of a connected component？有两个条件，一是这个方格处在grid的边界上，二是这个方格的上下左右四个方向的方格的颜色和自身不都一样。我的方法是分两步，第一步把和输入方格connect的所有方格都找出来，第二部就是依次判断这些connect的方格是否处于border，如果处于则修改颜色。component内部，在的话我们再次翻转-originColor,把它复原为originColor。经过这样的步骤之后，地图上所有标记为-originColor的点就是我们需要的边界了。我们将这些点重新标记为题目要求的color即可。https://buptwc.com/2019/05/02/Leetcode-1034-Coloring-A-Border/
给定一个二维矩阵grid，矩阵中的值代表在矩阵那处位置的颜色。
相连的颜色被认为是一个连通区域。
相连的颜色被认为是一个连通区域。
连通区域的边界是指那些和不属于该连通区域的块相连的部分，或者是处于整个矩阵的边界处的部分。
给定一个位置(r0, c0)，和一个颜色color。将(r0, c0)所在连通区域的颜色全部改成color，然后返回最终的矩阵grid.
示例 1:
输入: grid = [[1,1],[1,2]], r0 = 0, c0 = 0, color = 3
输出: [[3, 3], [3, 2]]
示例 2:
输入: grid = [[1,2,2],[2,3,2]], r0 = 0, c0 = 1, color = 3
输出: [[1, 3, 3], [2, 3, 3]]
示例 3:
输入: grid = [[1,1,1],[1,1,1],[1,1,1]], r0 = 1, c0 = 1, color = 2
输出: [[2, 2, 2], [2, 1, 2], [2, 2, 2]]
