1034. Coloring A Border
Сложение :
Вам дана целочисленная матричная сетка 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# решение
сопоставлено/оригинал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
}C++ решение
auto-draft, проверить перед отправкой#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 решение
auto-draft, проверить перед отправкойimport 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 решение
сопоставлено/оригиналvar 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 решение
сопоставлено/оригинал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
}Algorithm
Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.
Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.
Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.