959. Regions Cut By Slashes
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.
Дана сетка grid, представленная в виде строкового arrayа. return количество областей.
Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.
Esempio:
Input: grid = [" /","/ "]
Output: 2
C# soluzione
abbinato/originalepublic class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int Find(int x) {
if (parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}
public void Union(int x, int y) {
parent[Find(x)] = Find(y);
}
}
public class Solution {
public int RegionsBySlashes(string[] grid) {
int N = grid.Length;
DSU dsu = new DSU(4 * N * N);
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r][c];
if (val != '\\') {
dsu.Union(root + 0, root + 1);
dsu.Union(root + 2, root + 3);
}
if (val != '/') {
dsu.Union(root + 0, root + 2);
dsu.Union(root + 1, root + 3);
}
if (r + 1 < N) {
dsu.Union(root + 3, (root + 4 * N) + 0);
}
if (r - 1 >= 0) {
dsu.Union(root + 0, (root - 4 * N) + 3);
}
if (c + 1 < N) {
dsu.Union(root + 2, (root + 4) + 1);
}
if (c - 1 >= 0) {
dsu.Union(root + 1, (root - 4) + 2);
}
}
}
int ans = 0;
for (int x = 0; x < 4 * N * N; ++x) {
if (dsu.Find(x) == x) {
++ans;
}
}
return ans;
}
}C++ soluzione
bozza automatica, rivedere prima dell'invio#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class DSU {
vector<int>& parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int Find(int x) {
if (parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}
public void Union(int x, int y) {
parent[Find(x)] = Find(y);
}
}
class Solution {
public:
public int RegionsBySlashes(vector<string> grid) {
int N = grid.size();
DSU dsu = new DSU(4 * N * N);
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r][c];
if (val != '\\') {
dsu.Union(root + 0, root + 1);
dsu.Union(root + 2, root + 3);
}
if (val != '/') {
dsu.Union(root + 0, root + 2);
dsu.Union(root + 1, root + 3);
}
if (r + 1 < N) {
dsu.Union(root + 3, (root + 4 * N) + 0);
}
if (r - 1 >= 0) {
dsu.Union(root + 0, (root - 4 * N) + 3);
}
if (c + 1 < N) {
dsu.Union(root + 2, (root + 4) + 1);
}
if (c - 1 >= 0) {
dsu.Union(root + 1, (root - 4) + 2);
}
}
}
int ans = 0;
for (int x = 0; x < 4 * N * N; ++x) {
if (dsu.Find(x) == x) {
++ans;
}
}
return ans;
}
}Java soluzione
abbinato/originaleclass Solution {
public int regionsBySlashes(String[] grid) {
int N = grid.length;
DSU dsu = new DSU(4 * N * N);
for (int r = 0; r < N; ++r)
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r].charAt(c);
if (val != '\\') {
dsu.union(root + 0, root + 1);
dsu.union(root + 2, root + 3);
}
if (val != '/') {
dsu.union(root + 0, root + 2);
dsu.union(root + 1, root + 3);
}
if (r + 1 < N)
dsu.union(root + 3, (root + 4 * N) + 0);
if (r - 1 >= 0)
dsu.union(root + 0, (root - 4 * N) + 3);
if (c + 1 < N)
dsu.union(root + 2, (root + 4) + 1);
if (c - 1 >= 0)
dsu.union(root + 1, (root - 4) + 2);
}
int ans = 0;
for (int x = 0; x < 4 * N * N; ++x) {
if (dsu.find(x) == x)
ans++;
}
return ans;
}
}
class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}Go soluzione
abbinato/originaletype DSU struct {
parent []int
}
func NewDSU(N int) *DSU {
dsu := &DSU{parent: make([]int, N)}
for i := range dsu.parent {
dsu.parent[i] = i
}
return dsu
}
func (dsu *DSU) find(x int) int {
if dsu.parent[x] != x {
dsu.parent[x] = dsu.find(dsu.parent[x])
}
return dsu.parent[x]
}
func (dsu *DSU) union(x, y int) {
dsu.parent[dsu.find(x)] = dsu.find(y)
}
func regionsBySlashes(grid []string) int {
N := len(grid)
dsu := NewDSU(4 * N * N)
for r := 0; r < N; r++ {
for c := 0; c < N; c++ {
root := 4 * (r * N + c)
val := grid[r][c]
if val != '\\' {
dsu.union(root + 0, root + 1)
dsu.union(root + 2, root + 3)
}
if val != '/' {
dsu.union(root + 0, root + 2)
dsu.union(root + 1, root + 3)
}
if r + 1 < N {
dsu.union(root + 3, (root + 4 * N) + 0)
}
if r - 1 >= 0 {
dsu.union(root + 0, (root - 4 * N) + 3)
}
if c + 1 < N {
dsu.union(root + 2, (root + 4) + 1)
}
if c - 1 >= 0 {
dsu.union(root + 1, (root - 4) + 2)
}
}
}
ans := 0
for x := 0; x < 4 * N * N; x++ {
if dsu.find(x) == x {
ans++
}
}
return ans
}Algorithm
1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.
2⃣Используйте структуру объединения-поиска (DSU), чтобы find количество связанных компонентов.
3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей.
😎
Vacancies for this task
offerte attive with overlapping task tags are mostrati.
Non ci sono ancora offerte attive.