Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Uncategorized category for Can You Pass? by Moff
class QuickFindUF(object):
def __init__(self):
self.key = dict()
def push(self, p):
if p not in self.key:
self.key[p] = len(self.key) + 1
def connected(self, p, q):
return self.key.get(p) is not None and \
self.key.get(q) is not None and \
self.key.get(p) == self.key.get(q)
def union(self, p, q):
self.push(p)
self.push(q)
if self.connected(p, q):
return
pkey = self.key[p]
for node, key in self.key.items():
if key == pkey:
self.key[node] = self.key[q]
def can_pass(field, source, target):
delta = [(0, 1), (0, -1), (1, 0), (-1, 0)]
uf = QuickFindUF()
for i, row in enumerate(field):
for j, n in enumerate(row):
for ci, cj in ((i + di, j + dj) for di, dj in delta):
if 0 <= ci < len(field) and 0 <= cj < len(row) \
and field[i][j] == field[ci][cj]:
uf.union((i, j), (ci, cj))
return uf.connected(source, target)
Aug. 6, 2015
