Solution should be sum of coins collected on the way out of maze.
S : start point , G : end point , X : wall
maze text file
LEAST coins collected
-
11X11 maze
Solution is 6+8+6+2+4+2+3+3+9+9+0+8+3+6+9+5+2+5+1+4+1+7+0
+7+0+2+8+1+0+1+0+9+6+5+2+3+2+8+7+7+3+2+1+5+9 == 191
-
31X31 maze
1616 -
101X101 maze
2480
def bfs(x,y):
# deque library used for implementing queue
queue = deque()
queue.append((x,y))
while queue: # until queue is empty
x,y = queue.popleft()
for i in range(4): # check the location in 4 directions from the current location
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >=len(arr) or ny >= len(arr[0]): #outsize of maze
continue
if arr[nx][ny] == 'X': # walls
continue
if not visited[nx][ny]: # record shortest path only on first visit
if arr[nx][ny] == 'G': # if 'G', return the shortest path
return arr[x][y]
else:
arr[nx][ny] = str(int(arr[x][y]) + int(arr[nx][ny])) if arr[x][y] != 'S' else arr[nx][ny]
queue.append((nx,ny))
visited[x][y] = True
-
time
bfs-queue(deque library)
This BFS code uses the visited list variable to visit only nodes that have not been visited before. -
space
f:TextIOWrapper
arr:list -> n^2
line:str
visited:list[list[bool]] -> n^2
i:int
sx,sy:int
dx,dy:list[int]
x,y:int
queue:deque -> n
nx,ny:int