Leet Code Daily 2024-08-10 - Regions Cut By Slashes

const int kTop = 0, kLeft = 1, kRight = 2, kBottom = 3;

class Solution {
public:
    int root(vector<int>& fa, int x) {
        if (fa[x] != x) {
            fa[x] = root(fa, fa[x]);
        }
        return fa[x];
    }

    int regionsBySlashes(vector<string>& grid) {

        const int rows = grid.size(), cols = grid.front().size();
        auto id = [&](int r, int c, int d) -> int {
            return (r * cols + c) * 4 + d;
        };

        auto fa = vector<int>(rows * cols * 4);
        for (int i = 0; i < fa.size(); i++) {
            fa[i] = i;
        }
        auto merge = [&](int x, int y) { fa[root(fa, x)] = root(fa, y); };

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != '\\') {
                    merge(id(r, c, kTop), id(r, c, kLeft));
                    merge(id(r, c, kBottom), id(r, c, kRight));
                }
                if (grid[r][c] != '/') {
                    merge(id(r, c, kTop), id(r, c, kRight));
                    merge(id(r, c, kBottom), id(r, c, kLeft));
                }
                if (r > 0) {
                    merge(id(r, c, kTop), id(r - 1, c, kBottom));
                }
                if (r + 1 < rows) {
                    merge(id(r, c, kBottom), id(r + 1, c, kTop));
                }
                if (c > 0) {
                    merge(id(r, c, kLeft), id(r, c - 1, kRight));
                }
                if (c + 1 < cols) {
                    merge(id(r, c, kRight), id(r, c + 1, kLeft));
                }
            }
        }

        int ret = 1;
        for (int i = 1; i < fa.size(); i++) {
            if (root(fa, 0) != root(fa, i)) {
                merge(i, 0);
                ret++;
            }
        }
        return ret;
    }
};