Задача: 959. Regions Cut By Slashes Сложность: medium n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области. Дана сетка grid, представленная в виде строкового массива. Верните количество областей. Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '&#092;'. Пример: Input: grid = [" /","/ "] Output: 2 👨‍💻 Алгоритм: 1⃣Создайте 4NN узлов для каждой ячейки сетки и соедините их в соответствии с описанием. 2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов. 3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей. 😎 Решение: public 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 != '&#092;&#092;') { 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; } } Ставь 👍 и забирай 📚 Базу знаний