1391. Check if There is a Valid Path in a Grid

/**
 * Problem: LeetCode 1391 - Check if There is a Valid Path in a Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    static 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 i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    }

    public boolean hasValidPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        DSU dsu = new DSU(m * n);

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int val = grid[r][c];

                // Check right neighbor
                if (c + 1 < n) {
                    int rightVal = grid[r][c + 1];
                    boolean canGoRight = (val == 1 || val == 4 || val == 6);
                    boolean canReceiveLeft = (rightVal == 1 || rightVal == 3 || rightVal == 5);
                    if (canGoRight && canReceiveLeft) {
                        dsu.union(r * n + c, r * n + (c + 1));
                    }
                }

                // Check down neighbor
                if (r + 1 < m) {
                    int downVal = grid[r + 1][c];
                    boolean canGoDown = (val == 2 || val == 3 || val == 4);
                    boolean canReceiveUp = (downVal == 2 || downVal == 5 || downVal == 6);
                    if (canGoDown && canReceiveUp) {
                        dsu.union(r * n + c, (r + 1) * n + c);
                    }
                }
            }
        }

        return dsu.find(0) == dsu.find(m * n - 1);
    }
}

"""
Problem: LeetCode 1391 - Check if There is a Valid Path in a Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))

    def find(self, i: int) -> int:
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i: int, j: int) -> None:
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j


class Solution:
    def hasValidPath(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        dsu = DSU(m * n)

        for r in range(m):
            for c in range(n):
                val = grid[r][c]

                # Check right neighbor
                if c + 1 < n:
                    right_val = grid[r][c + 1]
                    can_go_right = val in (1, 4, 6)
                    can_receive_left = right_val in (1, 3, 5)
                    if can_go_right and can_receive_left:
                        dsu.union(r * n + c, r * n + (c + 1))

                # Check down neighbor
                if r + 1 < m:
                    down_val = grid[r + 1][c]
                    can_go_down = val in (2, 3, 4)
                    can_receive_up = down_val in (2, 5, 6)
                    if can_go_down and can_receive_up:
                        dsu.union(r * n + c, (r + 1) * n + c)

        return dsu.find(0) == dsu.find(m * n - 1)

/**
 * Problem: LeetCode 1391 - Check if There is a Valid Path in a Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <numeric>

using namespace std;

class Solution {
    struct DSU {
        vector<int> parent;

        DSU(int n) : parent(n) {
            iota(parent.begin(), parent.end(), 0);
        }

        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        void unite(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
            }
        }
    };

public:
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        DSU dsu(m * n);

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int val = grid[r][c];

                // Check right neighbor
                if (c + 1 < n) {
                    int rightVal = grid[r][c + 1];
                    bool canGoRight = (val == 1 || val == 4 || val == 6);
                    bool canReceiveLeft = (rightVal == 1 || rightVal == 3 || rightVal == 5);
                    if (canGoRight && canReceiveLeft) {
                        dsu.unite(r * n + c, r * n + (c + 1));
                    }
                }

                // Check down neighbor
                if (r + 1 < m) {
                    int downVal = grid[r + 1][c];
                    bool canGoDown = (val == 2 || val == 3 || val == 4);
                    bool canReceiveUp = (downVal == 2 || downVal == 5 || downVal == 6);
                    if (canGoDown && canReceiveUp) {
                        dsu.unite(r * n + c, (r + 1) * n + c);
                    }
                }
            }
        }

        return dsu.find(0) == dsu.find(m * n - 1);
    }
};

/**
 * Problem: LeetCode 1391 - Check if There is a Valid Path in a Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
class DSU {
    constructor(n) {
        this.parent = new Int32Array(n);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }

    find(i) {
        if (this.parent[i] === i) return i;
        this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }

    union(i, j) {
        const rootI = this.find(i);
        const rootJ = this.find(j);
        if (rootI !== rootJ) {
            this.parent[rootI] = rootJ;
        }
    }
}

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var hasValidPath = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dsu = new DSU(m * n);

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            const val = grid[r][c];

            // Check right neighbor
            if (c + 1 < n) {
                const rightVal = grid[r][c + 1];
                const canGoRight = (val === 1 || val === 4 || val === 6);
                const canReceiveLeft = (rightVal === 1 || rightVal === 3 || rightVal === 5);
                if (canGoRight && canReceiveLeft) {
                    dsu.union(r * n + c, r * n + (c + 1));
                }
            }

            // Check down neighbor
            if (r + 1 < m) {
                const downVal = grid[r + 1][c];
                const canGoDown = (val === 2 || val === 3 || val === 4);
                const canReceiveUp = (downVal === 2 || downVal === 5 || downVal === 6);
                if (canGoDown && canReceiveUp) {
                    dsu.union(r * n + c, (r + 1) * n + c);
                }
            }
        }
    }

    return dsu.find(0) === dsu.find(m * n - 1);
};