Pattern: BFS for shortest path on grid.
function labyrinth(grid, n, m):
find start (A) and end (B) positions
visited = 2D array of size n x m, all false
parentDir = 2D array of size n x m, all empty
q = queue
q.push(start)
visited[start.r][start.c] = true
while q is not empty:
(r, c) = q.pop()
if (r, c) == end:
break
for (dr, dc, dir) in [(−1,0,'U'), (1,0,'D'), (0,−1,'L'), (0,1,'R')]:
nr, nc = r + dr, c + dc
if inBounds(nr, nc) and grid[nr][nc] != '#' and not visited[nr][nc]:
visited[nr][nc] = true
parentDir[nr][nc] = dir
q.push((nr, nc))
if not visited[end.r][end.c]:
print "NO"
else:
print "YES"
path = backtrackPath(parentDir, start, end)
print path
Time: . Space: for visited and parent grids.