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: . Space: .