Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS solution in Clear category for Can You Pass? by libertypi
from operator import add
def can_pass(matrix, first, second):
moves = {(0, -1), (0, 1), (-1, 0), (1, 0)}
value = matrix[first[0]][first[1]]
maxH, maxW = len(matrix), len(matrix[0])
stack = [first]
visited = set()
while stack:
currentVert = stack.pop()
if currentVert in visited:
continue
visited.add(currentVert)
if currentVert == second:
return True
for move in moves:
x, y = map(add, currentVert, move)
if 0 <= x < maxH and 0 <= y < maxW and matrix[x][y] == value:
stack.append((x, y))
return False
if __name__ == '__main__':
assert can_pass(((0, 0, 0, 0, 0, 0),
(0, 2, 2, 2, 3, 2),
(0, 2, 0, 0, 0, 2),
(0, 2, 0, 2, 0, 2),
(0, 2, 2, 2, 0, 2),
(0, 0, 0, 0, 0, 2),
(2, 2, 2, 2, 2, 2),),
(3, 2), (0, 5)) == True, 'First example'
assert can_pass(((0, 0, 0, 0, 0, 0),
(0, 2, 2, 2, 3, 2),
(0, 2, 0, 0, 0, 2),
(0, 2, 0, 2, 0, 2),
(0, 2, 2, 2, 0, 2),
(0, 0, 0, 0, 0, 2),
(2, 2, 2, 2, 2, 2),),
(3, 3), (6, 0)) == False, 'First example'
July 15, 2020
Comments:
