Problem statement

https://binarysearch.com/problems/Connected-Road-to-Destination/

Solution

Almost the same as Leetcode 1970. Last Day Where You Can Still Cross.

Complexity

It is O(mn log(mn)) for time and O(mn) for space.

Code

class DSU:
    def __init__(self):
        self.p = {}

    def add(self, x):
        self.p[x] = x

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class  Solution :
    def solve (self, sx, sy, ex, ey, roads):
        beg, end = (sx, sy), (ex, ey)
        if abs(sx - ex) + abs(sy - ey) == 1: return 0

        dsu = DSU()
        dsu.add(beg)
        dsu.add(end)

        for i, (x, y) in enumerate(roads):
            dsu.add((x, y))
            for dx, dy in (1, 0), (-1, 0), (0, 1), (0, -1):
                if (x+dx, y+dy) in dsu.p:
                    dsu.union((x, y), (x+dx, y+dy))
                    if dsu.find(beg) == dsu.find(end):
                        return i + 1

        return -1