Labyrinth - Implementation

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: $O(N \cdot M)$. Space: $O(N \cdot M)$ for visited and parent grids.