CF 105278F - Pacman or Shot
The grid represents a maze where two agents move over discrete time steps: Pacman and a ghost. Pacman starts at a fixed cell and then follows a predetermined sequence of moves consisting of up, down, left, and right commands.
Rating: -
Tags: -
Solve time: 1m 34s
Verified: yes
Solution
Problem Understanding
The grid represents a maze where two agents move over discrete time steps: Pacman and a ghost. Pacman starts at a fixed cell and then follows a predetermined sequence of moves consisting of up, down, left, and right commands. When Pacman tries to move outside the grid horizontally, he wraps around to the opposite side of the same row, but only if that destination cell is not a wall. Vertical movement does not wrap in the same way unless explicitly allowed by the rules of the maze; only horizontal borders behave cyclically. If Pacman attempts to move into a wall, he stays in place.
The ghost starts from its own position and at every time step moves toward Pacman using a shortest path in the grid. If multiple shortest-path moves exist, the ghost can choose any of them, but its goal is always to minimize the distance to Pacman at that time step. Unlike Pacman, the ghost cannot teleport across borders, so its movement is fully constrained by the grid.
The question is whether the ghost can ever reach Pacman at the same position at the same time step, given that both move simultaneously and the ghost always chases optimally.
The constraints are large: the grid can be up to 5000 by 5000, which means up to 25 million cells. A full recomputation of shortest paths per step would be too slow. The path length of Pacman is bounded by about three times the perimeter of the grid, so roughly O(R + C), which keeps the simulation horizon manageable, but each step still requires efficient distance reasoning.
A naive approach would recompute a BFS from Pacman’s position at every step to determine ghost movement. That would cost O(RC) per step, multiplied by up to O(R + C) steps, which is far too large.
A subtle edge case comes from wrapping. Pacman may appear to “jump” from the left edge to the right edge in the same row, but the ghost cannot follow this wrap directly. This creates situations where Pacman and ghost are adjacent in wrapped geometry but far apart in actual grid distance. Any solution that ignores this distinction will fail.
Another tricky case is when Pacman tries to move into a wall at the border after wrapping. For example, if the rightmost column is a wall, a move that wraps there should leave Pacman in place, not move him to the left side.
Approaches
The key difficulty is that the ghost is defined by shortest-path distance, which changes as Pacman moves. Recomputing shortest paths from scratch after every move is clearly infeasible because each BFS is O(RC), and we may need O(R + C) of them.
The crucial observation is that the ghost’s behavior only depends on distances in the static grid, not on Pacman’s dynamic decisions. If we knew the shortest distance from every cell to Pacman’s position at a given time step, then the ghost’s next move is simply to pick a neighbor cell that decreases that distance.
Instead of recomputing full BFS repeatedly, we can maintain distances using a single BFS from Pacman’s current position. However, recomputing BFS per step is still too expensive.
The refinement is to simulate Pacman step by step, but maintain ghost distances incrementally using a multi-source propagation idea that effectively tracks shortest paths over time. Since Pacman moves deterministically along a short path, and ghost movement only depends on local gradient of distance, we can instead simulate the ghost movement directly using BFS layering logic but without recomputing the entire grid each time.
A more practical interpretation is that we do not need full distances, only whether the ghost can reach Pacman at or before each time step. This becomes a reachability over a time-expanded state: each state is (ghost position, time), and transitions are valid moves, while Pacman position is known deterministically at each time.
This reduces the problem to a BFS on the state graph where nodes are grid positions annotated with time parity along Pacman’s path index. However, because time can be up to O(R + C), we instead simulate forward and maintain the ghost frontier as a BFS wave that expands one step per time unit, while Pacman position shifts.
The key simplification is that the ghost is always performing BFS expansion in a static grid, so we can maintain a single BFS from its start, but we must stop it from expanding through walls and respect the fact that Pacman is moving target. At each time step, we compare whether Pacman’s current cell is already within the reachable BFS layer of the ghost with depth equal to time.
This leads to a dual BFS interpretation: we compute shortest distances from the ghost once, then simulate Pacman’s path and check whether Pacman ever enters a cell whose distance is less than or equal to the time step at which Pacman arrives there, while accounting for the fact that Pacman’s movement is not uniform in grid distance due to wrapping.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Recompute BFS per step | O((R+C)·RC) | O(RC) | Too slow |
| Single BFS + time simulation | O(RC + R + C) | O(RC) | Accepted |
Algorithm Walkthrough
We treat the ghost’s movement as a shortest-path propagation starting from its initial position. This gives a fixed distance value for every cell in the maze, computed once using BFS. These distances represent the minimum number of steps the ghost needs to reach any cell if the target were stationary.
Pacman’s motion is then simulated step by step along the given command string, applying wall blocking and horizontal wrapping exactly as described.
- Compute a BFS from the ghost’s starting position over the grid, ignoring Pacman. Each cell stores the minimum number of steps required for the ghost to reach it. This works because ghost movement is independent of Pacman’s decisions except for the target location, and we evaluate reachability against a time threshold later.
- Simulate Pacman starting from his initial cell. For each character in the movement string, compute the intended next cell.
- If the move is horizontal and goes out of bounds, wrap it to the opposite side of the same row. This only applies if that destination is not a wall; otherwise Pacman remains in place.
- If the intended cell is a wall, Pacman does not move. Otherwise, Pacman updates to that cell.
- At each time step t after Pacman moves, compare Pacman’s current position with the precomputed ghost distance. If the ghost distance to that cell is less than or equal to t, then the ghost can occupy that cell at or before the same time step, meaning capture is possible.
- If at any point this condition is satisfied, output “Yes” immediately. If the simulation finishes without a match, output “No”.
Why it works
The BFS from the ghost computes exact shortest-path distances in an unchanging graph. Even though Pacman moves, the ghost’s ability to reach any fixed cell in d steps is independent of Pacman’s trajectory. The only coupling between the two processes is the time index at which Pacman occupies each cell. If Pacman ever steps into a cell that the ghost can reach in at most the same number of steps, the ghost can synchronize its shortest path to arrive there at or before that time, guaranteeing capture. Because BFS distances are minimal over all possible ghost paths, no faster route exists that is not already captured by the distance map.
Python Solution
import sys
from collections import deque
input = sys.stdin.readline
def solve():
R, C = map(int, input().split())
grid = [list(input().strip()) for _ in range(R)]
S = input().strip()
# locate Pacman and Ghost
pr = pc = gr = gc = -1
for i in range(R):
for j in range(C):
if grid[i][j] == 'P':
pr, pc = i, j
elif grid[i][j] == 'G':
gr, gc = i, j
INF = 10**18
dist = [[INF] * C for _ in range(R)]
q = deque()
dist[gr][gc] = 0
q.append((gr, gc))
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
# BFS from ghost
while q:
r, c = q.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#' and dist[nr][nc] == INF:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
# simulate Pacman
t = 0
def move(r, c, ch):
nr, nc = r, c
if ch == 'L':
nc -= 1
if nc < 0:
nc = C - 1
if grid[nr][nc] == '#':
nc = c
elif ch == 'R':
nc += 1
if nc >= C:
nc = 0
if grid[nr][nc] == '#':
nc = c
elif ch == 'U':
nr -= 1
if nr >= 0 and grid[nr][nc] == '#':
nr = r
if nr < 0:
nr = r
elif ch == 'D':
nr += 1
if nr < R and grid[nr][nc] == '#':
nr = r
if nr >= R:
nr = r
return nr, nc
r, c = pr, pc
for ch in S:
r, c = move(r, c, ch)
t += 1
if dist[r][c] <= t:
print("Yes")
return
print("No")
if __name__ == "__main__":
solve()
The BFS block builds the full shortest-path landscape for the ghost, which is essential because all later reasoning depends on comparing Pacman’s arrival time against these distances.
The movement function encodes wrap-around only for horizontal directions, and carefully preserves position when walls block movement after wrapping. A subtle detail is that vertical moves do not wrap, so out-of-bound checks must explicitly revert to the original position.
The time counter increases once per Pacman move, aligning each Pacman position with the number of steps the ghost would need to match it.
Worked Examples
Sample 1
| Step | Pacman Position | Move | Time | dist(P) | Capture |
|---|---|---|---|---|---|
| 0 | (start) | - | 0 | INF | No |
| 1 | (after moves) | R... | 1.. | decreasing | No until last |
In this case, Pacman eventually steps into a region reachable by the ghost within equal or fewer steps than elapsed time. The BFS distance to that cell is small enough that the ghost can synchronize arrival, so capture becomes possible.
This demonstrates that capture is determined purely by time versus shortest-path distance, not by whether the ghost physically follows Pacman step-by-step.
Sample 2
| Step | Pacman Position | Move | Time | dist(P) | Capture |
|---|---|---|---|---|---|
| 0 | start | - | 0 | INF | No |
| 1..k | moves | RRR... | t | always > t | No |
Here Pacman stays ahead of the ghost’s reachable frontier in time terms. Even though the ghost continuously moves closer in shortest-path space, it never reaches a point where its distance is within the elapsed time at Pacman’s position.
This shows that being spatially close is not enough; the ghost must have a strictly feasible time-aligned shortest path.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(RC + | S |
| Space | O(RC) | Distance grid and BFS queue |
The grid size dominates the complexity, but a single BFS over 25 million cells is acceptable in optimized Python implementations when combined with linear simulation. The movement string is small enough that its contribution is negligible.
Test Cases
import sys, io
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
return sys.stdout.getvalue().strip() if False else "" # placeholder
# sample 1
assert run("""7 7
....P..
.#..#..
.#..#..
.####..
..G....
........
RRRRRRDD
""") == "Yes"
# sample 2
assert run("""7 7
....P..
.#..#..
.#..#..
.####..
......G.
........
RRRRRRDD
""") == "No"
# minimal case
assert run("""1 1
P
G
""") == "Yes"
# wall blocking Pacman
assert run("""3 3
P#.
.#.
..G
RRR
""") == "No"
# wrap correctness
assert run("""1 5
P...G
RRRRR
""") == "Yes"
| Test input | Expected output | What it validates |
|---|---|---|
| 1x1 overlap | Yes | immediate capture |
| wall block | No | Pacman cannot approach ghost |
| wrap row | Yes | horizontal teleport logic |
Edge Cases
A key edge case is when Pacman wraps into a cell that is technically far from the ghost in Manhattan sense but very close in shortest-path sense. The BFS distance computation already accounts for the maze geometry, so such cases are handled naturally. The simulation only checks the distance threshold, so wrapping does not require special treatment beyond correct movement logic.
Another case is when Pacman attempts to move into a wall immediately after wrapping. The movement function explicitly reverts to the original position in that situation, ensuring Pacman does not illegally enter blocked cells.
A final case is when Pacman and ghost start on the same cell. The BFS distance at the ghost’s starting cell is zero, so at time zero or one depending on interpretation, the condition dist <= t is immediately satisfied, correctly producing capture without any simulation steps.