959. Regions Cut By Slashes

leetcode medium

#array#csharp#leetcode#matrix#medium#search#string

Task

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]

Output: 2

C# solution

matched/original

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 != '\\') {
                    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++ 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.
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 solution

matched/original

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].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 solution

matched/original

type 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
}

Explanation

Algorithm

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей.

😎