Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1034.html
1034. Coloring A Border (Medium)
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
Related Topics: Depth-first Search
Similar Questions:
Solution 1. DFS
// OJ: https://leetcode.com/problems/coloring-a-border/
// Time: O(MN)
// Space: O(MN)
class Solution {
const int dirs[4][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
void dfs(vector<vector<int>> &G, int x, int y, int color) {
if (x < 0 || x >= G.size() || y < 0 || y >= G[0].size() || G[x][y] != color) return;
bool border = false;
for (auto &dir : dirs) {
int a = x + dir[0], b = y + dir[1];
if (a < 0 || a >= G.size() || b < 0 || b >= G[0].size() || (G[a][b] > 0 && G[a][b] != color)) {
border = true;
break;
}
}
G[x][y] = -color - (border ? 1 : 0);
for (auto &dir : dirs) dfs(G, x + dir[0], y + dir[1], color);
}
public:
vector<vector<int>> colorBorder(vector<vector<int>>& G, int r0, int c0, int color) {
int c = G[r0][c0];
dfs(G, r0, c0, c);
for (int i = 0; i < G.size(); ++i) {
for (int j = 0; j < G[0].size(); ++j) {
if (G[i][j] < 0) G[i][j] = G[i][j] == -c ? c : color;
}
}
return G;
}
};
Java
-
class Solution { public int[][] colorBorder(int[][] grid, int r0, int c0, int color) { final int BLOCK = -1; final int WHITE = 0; final int GRAY = 1; final int BLACK = 2; final int BORDER = 3; int componentColor = grid[r0][c0]; int rows = grid.length, columns = grid[0].length; int[][] states = new int[rows][columns]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (grid[i][j] != componentColor) states[i][j] = BLOCK; } } states[r0][c0] = GRAY; int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; Queue<int[]> queue = new LinkedList<int[]>(); queue.offer(new int[]{r0, c0}); while (!queue.isEmpty()) { int[] cell = queue.poll(); int row = cell[0], column = cell[1]; int count = 0; for (int[] direction : directions) { int newRow = row + direction[0], newColumn = column + direction[1]; if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) { if (states[newRow][newColumn] != BLOCK) count++; if (states[newRow][newColumn] == WHITE) { states[newRow][newColumn] = GRAY; queue.offer(new int[]{newRow, newColumn}); } } } if (count == 4) states[row][column] = BLACK; else states[row][column] = BORDER; } for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (states[i][j] == BORDER) grid[i][j] = color; } } return grid; } } -
// OJ: https://leetcode.com/problems/coloring-a-border/ // Time: O(MN) // Space: O(MN) class Solution { const int dirs[4][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; void dfs(vector<vector<int>> &G, int x, int y, int color) { if (x < 0 || x >= G.size() || y < 0 || y >= G[0].size() || G[x][y] != color) return; bool border = false; for (auto &dir : dirs) { int a = x + dir[0], b = y + dir[1]; if (a < 0 || a >= G.size() || b < 0 || b >= G[0].size() || (G[a][b] > 0 && G[a][b] != color)) { border = true; break; } } G[x][y] = -color - (border ? 1 : 0); for (auto &dir : dirs) dfs(G, x + dir[0], y + dir[1], color); } public: vector<vector<int>> colorBorder(vector<vector<int>>& G, int r0, int c0, int color) { int c = G[r0][c0]; dfs(G, r0, c0, c); for (int i = 0; i < G.size(); ++i) { for (int j = 0; j < G[0].size(); ++j) { if (G[i][j] < 0) G[i][j] = G[i][j] == -c ? c : color; } } return G; } }; -
class Solution: def colorBorder( self, grid: List[List[int]], row: int, col: int, color: int ) -> List[List[int]]: m, n = len(grid), len(grid[0]) vis = [[False] * n for _ in range(m)] def dfs(i, j, color): vis[i][j] = True old_color = grid[i][j] for a, b in [[-1, 0], [1, 0], [0, -1], [0, 1]]: x, y = a + i, b + j if 0 <= x < m and 0 <= y < n: if not vis[x][y]: if grid[x][y] == old_color: dfs(x, y, color) else: grid[i][j] = color else: grid[i][j] = color dfs(row, col, color) return grid ############ # 1034. Coloring A Border # https://leetcode.com/problems/coloring-a-border/ class Solution: def colorBorder(self, grid, row, col, color): seen, rows, cols = set(), len(grid), len(grid[0]) def dfs(x, y): if (x, y) in seen: return True if not (0 <= x < rows and 0 <= y < cols and grid[x][y] == grid[row][col]): return False seen.add((x, y)) if dfs(x + 1, y) + dfs(x - 1, y) + dfs(x, y + 1) + dfs(x, y - 1) < 4: grid[x][y] = color return True dfs(row, col) return grid