Maze I
https://leetcode.com/problems/the-maze/
- BFS and DFS both are applicable to here. Problem is just requesting for True/False for possible stop at destination.
- BFS is used here as it serves as recipe for Maze II and Maze III as well.
- What is a stop: cant progress further in present direction i.e. hit a wall or grid boundary.
- What is a direction: direction is up say "u" if (-1, 0) is applied at every move similarly for down= (1,0), left(0,-1) right(0,1)
- Choosing candidate neighbourers:
a. All neighbourers which are maze[i][j] == 0 and not visited already. - How to check for visited already? depends on node uniqueness i.e. (i,j) or (i, j,direction)
a. Do not care if given not is not a stop node do consider as candidate.
b. If a "stop node" then repeating movement in same direction if before then it is a loop.
#receipe for candidates
seen=set()
queue=deque()
def getneigh(i, j, maze):
tmp = [(i+x, j+y) for x,y in [(1,0), (0,1), (-1,0), (0,-1)]]
neig=[]
for x, y in tmp:
if not (x < 0 or x >= len(maze) or y < 0 or y >= len(maze[0])) and maze[x][y] == 0:
neig.append((x,y))
return neig
def getoptions(i, j, maze,queue,seen):
neig = getneigh(i,j, maze)
for x, y in neig:
if x < i:
direction=0
elif x > i:
direction=1
elif y > j:
direction=2
else:
direction=3
node=(i, j, direction)
if node not in seen:
queue.append(node)
seen.add(node) Full solution: getoptions(start[0], start[1], maze,queue,seen)
while queue:
i, j, direction = queue.popleft()
if direction == 0: #up
i-=1
while i >= 0 and maze[i][j] != 1: #hit end
seen.add((i,j,direction))
i-=1
i+=1 #one step back
elif direction == 1: #down
i+=1
while i < len(maze) and maze[i][j] != 1: #hit end
seen.add((i,j,direction))
i+=1
i-=1 #one step back
elif direction == 2: #right
j+=1
while j < len(maze[0]) and maze[i][j] != 1: #hit end
seen.add((i,j,direction))
j+=1
j-=1 #one step back
elif direction == 3: #left
j-=1
while j >= 0 and maze[i][j] != 1: #hit end
seen.add((i,j,direction))
j-=1
j+=1 #one step back
if i == destination[0] and j == destination[1]: #is it destination ?
return True
getoptions(i,j,maze,queue,seen)
return FalseMaze II
https://leetcode.com/problems/the-maze-ii/
Here need to choose shortest path:
- cant use queue as processing done per roll i.e. number of cells rolles per "turn" is varied.
- with queue we dequeue at a turn basis
- Need to use a heap(priority-queue or min-heap) datastructure with we process smaller path length independent of number of turns taken so far
heap=[]
getoptions(start[0], start[1], maze,heap,0,0)- Options for turn at a stop node is based on if it were visited with a larger path lenth before or unvisited
- So need to track shortest distance to each stop node
- Use a dictionary:
sp = defaultdict(lambda:sys.maxsize)
sp[(start[0], start[1])]=0#recepie for candidates is little different
def getoptions(i, j, maze,heap,pathL,turn):
neig = getneigh(i,j, maze)
for x, y in neig:
if x < i:
direction=0
elif x > i:
direction=1
elif y > j:
direction=2
else:
direction=3
heapq.heappush(heap,[pathL, i, j, direction, turn])
```
#We only call getoptions if this stop node as been not visited or has been visited with higher path len if sp[(i,j)] > pathL:
sp[(i,j)] = pathL
getoptions(i,j,maze,heap,pathL,turn+1)
Full solution: getoptions(start[0], start[1], maze,heap,0,0)
minPl = sys.maxsize
sp = defaultdict(lambda:sys.maxsize)
sp[(start[0], start[1])]=0
while heap:
pathL, i, j, direction, turn = heapq.heappop(heap)
if direction == 0: #up
i-=1
while i >= 0 and maze[i][j] != 1: #hit end
pathL+=1
i-=1
i+=1 #one step back
elif direction == 1: #down
i+=1
while i < len(maze) and maze[i][j] != 1: #hit end
pathL+=1
i+=1
i-=1 #one step back
elif direction == 2: #right
j+=1
while j < len(maze[0]) and maze[i][j] != 1: #hit end
pathL+=1
j+=1
j-=1 #one step back
elif direction == 3: #left
j-=1
while j >= 0 and maze[i][j] != 1: #hit end
pathL+=1
j-=1
j+=1 #one step back
if i == destination[0] and j == destination[1]: #is it destination ?
if minPl > pathL:
minPl = pathL
if sp[(i,j)] > pathL:
sp[(i,j)] = pathL
getoptions(i,j,maze,heap,pathL,turn+1)
if minPl == sys.maxsize:
return -1
return minPl
3 Maze III
https://leetcode.com/problems/the-maze-iii/
1. Here similar to Maze II need to use heap datastructure
2. At each turn need to add the direction chosen to the next node we post to the heap def dts(direction):
if direction == 0:
return "u"
if direction == 1:
return "d"
if direction == 2:
return "r"
if direction == 3:
return "l"
def getoptions(i, j, maze,heap,pathL,commands):
neig = getneigh(i,j, maze)
for x, y in neig:
if x < i:
direction=0
elif x > i:
direction=1
elif y > j:
direction=2
else:
direction=3
heapq.heappush(heap,[pathL, i, j, direction,commands+dts(direction)]) #<<<<<<<<<<<<<<<
3. Roll same way as Maze II but hold need not be a stop node
4. It can be any node in middle of a roll.
5. If hole is found in middle of roll stop and dont roll any further
6. If hole is found need to update the shortest command found so far
7. if command is same length update iff it is lexicographically smaller if i == destination[0] and j == destination[1]: #is it destination ?
if minPl >= pathL:
minPl = pathL
if res > commands:
res=commands
found=True8. unlike Maze II have to consider options with same path lenght because commands could be lex smaller: if sp[(i,j)] >= pathL: # not > but >= because commands could be lex smaller
sp[(i,j)] = pathL
getoptions(i,j,maze,heap,pathL,commands)
Full solution while heap:
pathL, i, j, direction,commands = heapq.heappop(heap)
found=False
if direction == 0: #up
i-=1
while i >= 0 and maze[i][j] != 1 and found == False: #hit end
pathL+=1
if i == destination[0] and j == destination[1]: #is it destination ?
if minPl >= pathL:
minPl = pathL
if res > commands:
res=commands
found=True
i-=1
i+=1 #one step back
elif direction == 1: #down
i+=1
while i < len(maze) and maze[i][j] != 1 and found == False: #hit end
pathL+=1
if i == destination[0] and j == destination[1]: #is it destination ?
if minPl >= pathL:
minPl = pathL
#res=commands
if res > commands:
res=commands
found=True
i+=1
i-=1 #one step back
elif direction == 2: #right
j+=1
while j < len(maze[0]) and maze[i][j] != 1 and found == False: #hit end
pathL+=1
if i == destination[0] and j == destination[1]: #is it destination ?
if minPl >= pathL:
minPl = pathL
if res > commands:
res=commands
found=True
j+=1
j-=1 #one step back
elif direction == 3: #left
j-=1
while j >= 0 and maze[i][j] != 1 and found == False: #hit end
pathL+=1
if i == destination[0] and j == destination[1]: #is it destination ?
if minPl >= pathL:
minPl = pathL
if res > commands:
res=commands
found=True
j-=1
j+=1 #one step back
if found:
continue
if sp[(i,j)] >= pathL:
sp[(i,j)] = pathL
getoptions(i,j,maze,heap,pathL,commands)
if minPl == sys.maxsize:
return "impossible"
return res Comments (0)