1034. Coloring A Border
leetcode medium
Task
Сложение :
Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.
Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.
Пример:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]
C# solution
matched/originalfunc colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
originalColor := grid[row][col]
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
borders := [][]int{}
var dfs func(r, c int)
dfs = func(r, c int) {
visited[r][c] = true
isBorder := false
for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
nr, nc := r+dir[0], c+dir[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n {
if !visited[nr][nc] {
if grid[nr][nc] == originalColor {
dfs(nr, nc)
} else {
isBorder = true
}
}
} else {
isBorder = true
}
}
if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
borders = append(borders, []int{r, c})
}
}
dfs(row, col)
for _, border := range borders {
grid[border[0]][border[1]] = color
}
return grid
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
originalColor := grid[row][col]
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
borders := [][]int{}
var dfs func(r, c int)
dfs = func(r, c int) {
visited[r][c] = true
isBorder := false
for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
nr, nc := r+dir[0], c+dir[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n {
if !visited[nr][nc] {
if grid[nr][nc] == originalColor {
dfs(nr, nc)
} else {
isBorder = true
}
}
} else {
isBorder = true
}
}
if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
borders = append(borders, []int{r, c})
}
}
dfs(row, col)
for _, border := range borders {
grid[border[0]][border[1]] = color
}
return grid
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
func colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
originalColor := grid[row][col]
visited := make([][]boolean, m)
for i := range visited {
visited[i] = make([]boolean, n)
}
borders := [][]int{}
var dfs func(r, c int)
dfs = func(r, c int) {
visited[r][c] = true
isBorder := false
for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
nr, nc := r+dir[0], c+dir[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n {
if !visited[nr][nc] {
if grid[nr][nc] == originalColor {
dfs(nr, nc)
} else {
isBorder = true
}
}
} else {
isBorder = true
}
}
if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
borders = append(borders, []int{r, c})
}
}
dfs(row, col)
for _, border := range borders {
grid[border[0]][border[1]] = color
}
return grid
}JavaScript solution
matched/originalvar colorBorder = function(grid, row, col, color) {
const m = grid.length, n = grid[0].length;
const originalColor = grid[row][col];
const visited = new Array(m).fill(null).map(() => new Array(n).fill(false));
const borders = [];
const dfs = (r, c) => {
visited[r][c] = true;
let isBorder = false;
for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (!visited[nr][nc]) {
if (grid[nr][nc] === originalColor) {
dfs(nr, nc);
} else {
isBorder = true;
}
}
} else {
isBorder = true;
}
}
if (isBorder || r === 0 || r === m - 1 || c === 0 || c === n - 1) {
borders.push([r, c]);
}
};
dfs(row, col);
for (const [r, c] of borders) {
grid[r][c] = color;
}
return grid;
};Go solution
matched/originalfunc colorBorder(grid [][]int, row int, col int, color int) [][]int {
m, n := len(grid), len(grid[0])
originalColor := grid[row][col]
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
borders := [][]int{}
var dfs func(r, c int)
dfs = func(r, c int) {
visited[r][c] = true
isBorder := false
for _, dir := range [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} {
nr, nc := r+dir[0], c+dir[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n {
if !visited[nr][nc] {
if grid[nr][nc] == originalColor {
dfs(nr, nc)
} else {
isBorder = true
}
}
} else {
isBorder = true
}
}
if isBorder || r == 0 || r == m-1 || c == 0 || c == n-1 {
borders = append(borders, []int{r, c})
}
}
dfs(row, col)
for _, border := range borders {
grid[border[0]][border[1]] = color
}
return grid
}Explanation
Algorithm
Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.
Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.
Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.
😎