Monsters - Implementation

Pattern: Multi-source BFS followed by player BFS.

function monsters(grid, n, m):
    monsterTime = 2D array of size n x m, all infinity
    playerTime = 2D array of size n x m, all infinity

    // Phase 1: Multi-source BFS from all monsters
    q = queue
    for each monster position M:
        q.push(M)
        monsterTime[M.r][M.c] = 0

    while q is not empty:
        (r, c) = q.pop()
        for (nr, nc) in neighbors(r, c):
            if grid[nr][nc] != '#' and monsterTime[nr][nc] == infinity:
                monsterTime[nr][nc] = monsterTime[r][c] + 1
                q.push((nr, nc))

    // Phase 2: BFS from player
    q.push(start)
    playerTime[start.r][start.c] = 0

    while q is not empty:
        (r, c) = q.pop()
        if onBoundary(r, c):
            print "YES"
            print backtrackPath(r, c)
            return
        for (nr, nc) in neighbors(r, c):
            if grid[nr][nc] != '#' and playerTime[nr][nc] == infinity:
                if playerTime[r][c] + 1 < monsterTime[nr][nc]:
                    playerTime[nr][nc] = playerTime[r][c] + 1
                    q.push((nr, nc))

    print "NO"

Time: $O(N \cdot M)$. Space: $O(N \cdot M)$.