Problem:
A 2D maze(of size RxC) has R rows and C columns. Each empty cell is marked by ‘O' (letter O) and the one with a barrier is marked by ‘#’. Two coordinates from the Maze(a,b) and (x,y). Currently, the starting point is at (a,b) and the destination is (x,y).
Move only in the following directions.
L: move to left cell from the current cell
R: move to right cell from the current cell
U: move to upper cell from the current cell
D: move to the lower cell from the current cell
Example:
Maze= [
['O', 'O', 'O', 'O', 'O'],
['O', 'O', '#', 'O', 'O'],
['O', 'O', 'O', 'O', 'O'],
['#', 'O', '#', '#', 'O'],
['O', '#', 'O', 'O', 'O']
]
Example #1
Input: Maze, (0,2), (2,2)
Output: ([(0, 2), (0, 1), (1, 1), (2, 1), (2, 2)], 'LDDR')
Example #2
Input: Maze, (0,0), (4,4)
Output: ([(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)], 'RRRRDDDD')
Example #3
Input: Maze, (0,0), (4,0)
Output: None
- Not an empty list, but the None object.
So I decided to do BSF for this problem but now I'm stuck. I don't know when should I insert the indices of each position in the path. Since I have to output a list of tuples(starting with the source and ending with the destination) as well as return a set of possible directions as well in the form of a string. Any guidance would be appreciated, thank you.
Here is my code:
def puzzle(Board, Source, Destination):
# if Source is None or Source not in Board:
# return Source
dx = [-1, 1, 0, 0]
dy = [0, 0 , 1, -1]
visited = [[False]*cols for i in range(rows)]
distances = {vertex : float('inf') for vertex in range(rows)}
reached_end = False
distances[Source] = 0
queue = deque()
queue.append((currentRow,currentCol))
visited[currentRow][currentCol] = True
while queue:
r,c = queue.popleft()
path = (r,c)
if(path == Destination):
reached_end = True
return
for neighbor in range(0,4):
rr = r dx[neighbor]
cc = c dy[neighbor]
if (rr < 0 or cc < 0):
continue
if (rr >= rows or cc >= cols):
continue
if visited[rr][cc]:
continue
if Board[rr][cc] == '#':
continue
queue.append((rr,cc))
visited[rr][cc] = True
CodePudding user response:
One way to do this, is to add the list of moves ("LDDR...") to the tuple that is queued. Then when the destination is found, you can build the coordinates from that.
Here is your code with those adaptations:
def puzzle(Board, Source, Destination):
if Source is None or Source not in Board:
return
cols = len(Board[0])
rows = len(Board)
currentRow,currentCol = Source
dx = [-1, 1, 0, 0]
dy = [0, 0 , 1, -1]
dirs = "UDRL"
visited = [[False]*cols for i in range(rows)]
distances = {vertex : float('inf') for vertex in range(rows)}
distances[Source] = 0
queue = deque()
queue.append((currentRow,currentCol, ""))
visited[currentRow][currentCol] = True
while queue:
r,c,moves = queue.popleft()
path = (r,c)
if path == Destination:
path = [Source]
r,c = Source
for move in moves:
i = dirs.index(move)
r = dx[i]
c = dy[i]
path.append((r,c))
return path, moves
for neighbor in range(0,4):
rr = r dx[neighbor]
cc = c dy[neighbor]
if (rr < 0 or cc < 0):
continue
if (rr >= rows or cc >= cols):
continue
if visited[rr][cc]:
continue
if Board[rr][cc] == '#':
continue
queue.append((rr,cc,moves dirs[neighbor]))
visited[rr][cc] = True