Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Can You Pass? by sawako.oono
from collections import deque
def can_pass(matrix, first, second):
Ly=len(matrix)
Lx=len(matrix[0])
q=deque()
q.append([first])
seen=[]
while q:
path=q.pop()
if path in seen:
continue
else:
seen.append(path.copy())
if path[-1]==second:
return True
Y=path[-1][0]
X=path[-1][1]
value=matrix[Y][X]
for y,x in (1,0),(-1,0),(0,1),(0,-1):
path_c=path.copy()
if 0<=X+x<=Lx-1 and 0<=Y+y<=Ly-1:
if (Y+y,X+x) not in path and value==matrix[Y+y][X+x]:
path_c.append((Y+y,X+x))
q.append(path_c)
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'
June 25, 2021
