You are given integers sx, sy, ex, ey and two-dimensional list of integers roads. You are currently located at coordinate (sx, sy) and want to move to destination (ex, ey). Each element in roads contains (x, y) which is a road that will be added at that coordinate. Roads are added one by one in order. You can only move to adjacent (up, down, left, right) coordinates if there is a road in that coordinate or if it's the destination coordinate. For example, at (x, y) we can move to (x + 1, y) if (x + 1, y) is a road or the destination.
Return the minimum number of roads in order that must be added before there is a path consisting of roads that allows us to get to (ex, ey) from (sx, sy). If there is no solution, return -1.
Constraints
0 ≤ n ≤ 100,000 where n is the length of roads
Example 1
Input
sx = 0
sy = 0
ex = 1
ey = 2
roads = [
[9, 9],
[0, 1],
[0, 2],
[0, 3],
[3, 3]
]
Output
3
Explanation
We need to add the first three roads which allows us to go from (0, 0), (0, 1), (0, 2), (1, 2). Note that we must take (9, 9) since roads must be added in order.
class Solution:
def solve(self, sx, sy, ex, ey, roads):
def possible(mid):
dic = set([(sx, sy), (ex, ey)])
visited = set()
q = collections.deque([(sx, sy)])
for x, y in roads[:mid]:
dic.add((x, y))
while q:
x, y = q.popleft()
if (x, y) in visited: continue
visited.add((x, y))
if (x, y) == (ex, ey): return True
for dx, dy in [(1,0),(-1,0), (0,1), (0,-1)]:
if (x + dx, y + dy) in dic:
q.append((x + dx, y + dy))
return False
l, r = 0, len(roads)
while l <= r:
mid = (l + r) // 2
if possible(mid):
r = mid - 1
else:
l = mid + 1
return -1 if l > len(roads) else l
由于需要加边，因此对模板需要进行一点小小调整，增加 add(x) api 用于加点，功能是将 x 加入到图中，接下来使用 union 加边即可。
代码
代码支持：Python3
Python Code:
class UF:
def __init__(self):
self.parent = {}
self.cnt = 0
def add(self, i):
self.parent[i] = i
self.cnt += 1
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
return x
def union(self, p, q):
if p not in self.parent or q not in self.parent: return
if self.connected(p, q): return
leader_p = self.find(p)
leader_q = self.find(q)
self.parent[leader_p] = leader_q
self.cnt -= 1
def connected(self, p, q):
return self.find(p) == self.find(q)
class Solution:
def solve(self, sx, sy, ex, ey, roads):
start = (sx, sy)
end = (ex, ey)
# 注意特判
for dx, dy in [(0, 0), (1,0), (-1,0), (0,1), (0,-1)]:
x = sx + dx
y = sy + dy
if (x, y) == (ex, ey): return 0
uf = UF()
uf.add(start)
uf.add(end)
for i, road in enumerate(map(tuple, roads)):
uf.add(road)
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
x = road[0] + dx
y = road[1] + dy
uf.union(road, (x, y))
if uf.connected(start, end):
return i + 1
return -1
