题目
Task
You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return the minimal number of steps to exit position [N-1, N-1] if it is possible to reach the exit from the starting position. Otherwise, return false in JavaScript/Python and -1 in C++/C#/Java.
Empty positions are marked .. Walls are marked W. Start and exit positions are guaranteed to be empty in all test cases.
我的答案
from collections import deque
from math import sqrt, floor
dirc = [[0, 1], [0, -1], [1, 0], [-1, 0]]
d = deque(maxlen=500)
def BFS(n, maze):
while len(d) > 0:
d0 = d.popleft()
for i in range(4):
x = d0[0] + dirc[i][0]
y = d0[1] + dirc[i][1]
if x < 0 or x >= n or y < 0 or y >= n:
continue
if maze[x * n + y] == 'W':
continue
if x == n - 1 and y == n - 1:
return d0[2] + 1
maze[x * n + y] = 'W'
d.append([x, y, d0[2] + 1])
return False
def path_finder(maze):
n = floor(sqrt(len(maze)))
if n == 1:
return 0
else:
maze = [i for i in list(maze) if i !='\n']
while len(d) > 0:
d.pop()
d.append([0, 0, 0])
maze[0] = 'W'
return BFS(n, maze)
其他精彩答案
def path_finder(maze):
lst = maze.split('\n')
X, Y = len(lst)-1, len(lst[0])-1
seen = {(x,y) for x,row in enumerate(lst) for y,c in enumerate(row) if c=='W'} | {(0,0)}
end, bag, turn = (X,Y), {(0,0)}, 0
while bag and end not in bag:
bag = { (a,b) for a,b in {(x+dx,y+dy) for x,y in bag for dx,dy in ((0,1), (0,-1), (1,0), (-1,0))}
if 0 <= a <= X and 0 <= b <= Y} - seen
seen |= bag
turn += 1
return bool(bag) and turn
def path_finder(maze):
maze = list(map(list, maze.splitlines()))
lenmaze_y, lenmaze_x = len(maze), len(maze[0])
queue = [(0, 0, 0)]
while queue:
y,x,cnt = queue.pop(0)
if x >= 0 and y >= 0 and x < lenmaze_x and y < lenmaze_y:
if maze[y][x] == '.':
maze[y][x] = cnt
directions = [(1, 0),(0, 1),(-1, 0),(0, -1)]
for direction_y, direction_x in directions:
queue.append((y + direction_y, x + direction_x, cnt+1))
if x == lenmaze_x-1 and y == lenmaze_y-1:
return maze[y][x]
return False
