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 alterGNU
# MATRICE:
# - [a, b] : a:value ; b:state (0:not visited, 1:visited)
# convert tuple grid to matrix
def convert_mat(matrix,stop):
(l, c) = (len(matrix), len(matrix[0]))
grid = []
for i in range(l):
row = []
for j in range(c):
row.append([matrix[i][j],0])
grid.append(row)
return grid
def can_pass(matrix, first, second):
# case if start-value is different end-value ==> False
if matrix[first[0]][first[1]]!=matrix[second[0]][second[1]]:return False
# Convert tuple grid to matrix
mat = convert_mat(matrix,second)
queue = [] # list of cases to search
# Functions
up = lambda c: (c[0]-1,c[1]) if c[0]-1 >= 0 else None
right = lambda c: (c[0],c[1]+1) if c[1]+1 < len(matrix[0]) else None
down = lambda c: (c[0]+1,c[1]) if c[0]+1 < len(matrix) else None
left = lambda c: (c[0],c[1]-1) if c[1]-1 >= 0 else None
adjacent = lambda c: [ up(c), right(c), down(c), left(c) ]
enqueue = lambda c: queue.append(c)
dequeue = lambda : queue.pop(0)
visitable = lambda c: (mat[c[0]][c[1]][0] == matrix[first[0]][first[1]])and(mat[c[0]][c[1]][1]!=1)
def visited(point):
mat[point[0]][point[1]][1] = 1
# Init & Start searching path
start = first
enqueue(first)
while len(queue) > 0:
elem = dequeue()
visited(elem)
neighbours = [n for n in adjacent(elem) if (n != None)and(visitable(n)) ]
for n in neighbours:
if n == second:
return True
if mat[n[0]][n[1]][1] == 0: queue.append(n)
# If stop-case not found: Then impossible path == return False
return False
June 6, 2021
