Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Branch: master
Fetching contributors…

Cannot retrieve contributors at this time

74 lines (58 sloc) 2.062 kB
from collections import deque
EMPTY = 0
LINE = 1
FILLED = 2
ADJ_NODES = [(-1, 0), (0, -1), (1, 0), (0, 1)]
class Node(object):
def __init__(self, x, y, offset, distance):
self.val = (x, y, offset, distance)
def __repr__(self):
return str(self.val)
def __hash__(self):
return self.val[0:2].__hash__()
def __eq__(self, other):
return self.val[0:2] == other
def __cmp__(self, other):
return self.val[3].__cmp__(other.val[3])
def __getitem__(self, key):
return self.val[key]
class PathFinder(object):
def __init__(self, start, end, grid):
self.grid = grid
self.start = tuple(start)
self.end = tuple(end)
self.distance = abs(self.start[0] - self.end[0]) + \
abs(self.start[1] - self.end[1])
def _getAdjNodes(self, node):
res = set()
for offset in ADJ_NODES:
row = node[0] + offset[0]
col = node[1] + offset[1]
if self.grid.isEmpty(row, col) \
or (row, col) == self.end:
distance = abs(row - self.end[0]) + abs(col - self.end[1])
res.add(Node(row, col, offset, distance))
return res
def solve(self):
a = (self.start) + (None, self.distance)
opened = set([Node(*a)])
closed = {}
running = True
while running:
if not opened:
raise ValueError("Path not found!")
best = min(opened)
running = bool(best[3])
closed[best[0:2]] = best[2]
opened.discard(best)
adj_nodes = self._getAdjNodes(best)
opened.update(adj_nodes.difference(closed))
res = deque()
curr_node = self.end
while curr_node != self.start:
offset = closed[curr_node]
res.append(offset)
curr_node = (curr_node[0] - offset[0],
curr_node[1] - offset[1])
res.reverse()
return res
Jump to Line
Something went wrong with that request. Please try again.