Video Solution

By David Zhou

Explanation

Because the monsters move optimally, if a monster can reach a location in the maze before A, then A may never move to that spot. Thus, for A to enter a spot, the distance from that location to A must be less than the distance from that location to the nearest monster. Knowing this, we may BFS to find all locations that are visitable by A. This will run in $NM$ time because each location will be visited a constant amount of times.

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
from collections import deque

n, m = map(int, input().split())
maze = [input() for _ in range(n)]

# distance grids tracking minimum steps from monsters and person respectively
dist_monster = [[float("inf")] * m for _ in range(n)]
dist_person = [[float("inf")] * m for _ in range(n)]

# direction[r][c] stores which move was used to reach (r, c)