| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1253837 | shawnchang51 | Maze (JOI23_ho_t3) | Pypy 3 | 0 ms | 0 KiB |
from collections import deque
import sys
def solve():
R, C, N = map(int, input().split())
Sr, Sc = map(int, input().split())
Gr, Gc = map(int, input().split())
```
# Convert to 0-indexed
Sr -= 1
Sc -= 1
Gr -= 1
Gc -= 1
grid = []
for _ in range(R):
grid.append(input().strip())
def has_path(white_cells):
"""Check if there's a path from start to goal using only white cells"""
if (Sr, Sc) not in white_cells or (Gr, Gc) not in white_cells:
return False
visited = set()
queue = deque([(Sr, Sc)])
visited.add((Sr, Sc))
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
r, c = queue.popleft()
if r == Gr and c == Gc:
return True
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < R and 0 <= nc < C and
(nr, nc) not in visited and (nr, nc) in white_cells):
visited.add((nr, nc))
queue.append((nr, nc))
return False
# Get initial white cells
initial_white = set()
for i in range(R):
for j in range(C):
if grid[i][j] == '.':
initial_white.add((i, j))
# Check if already possible
if has_path(initial_white):
return 0
if N == 1:
# Special case: each operation paints a single cell
# Use 0-1 BFS (Dijkstra with only 0 and 1 weights)
dist = [[float('inf')] * C for _ in range(R)]
dist[Sr][Sc] = 0 if (Sr, Sc) in initial_white else 1
dq = deque([(Sr, Sc)])
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while dq:
r, c = dq.popleft()
if r == Gr and c == Gc:
return dist[r][c]
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C:
cost = 0 if (nr, nc) in initial_white else 1
new_dist = dist[r][c] + cost
if new_dist < dist[nr][nc]:
dist[nr][nc] = new_dist
if cost == 0:
dq.appendleft((nr, nc))
else:
dq.append((nr, nc))
return dist[Gr][Gc] if dist[Gr][Gc] != float('inf') else -1
# For general case with N > 1
# Generate all possible stamp positions
stamp_positions = []
for a in range(R - N + 1):
for b in range(C - N + 1):
stamp_positions.append((a, b))
def apply_stamp(white_cells, a, b):
"""Apply stamp at position (a,b) and return new white cells set"""
new_white = white_cells.copy()
for i in range(a, a + N):
for j in range(b, b + N):
new_white.add((i, j))
return new_white
# BFS on grid configurations
# State: (frozenset of white cells, number of operations)
queue = deque([(frozenset(initial_white), 0)])
visited_configs = set([frozenset(initial_white)])
# Adaptive search depth based on problem size
if R * C <= 1000:
max_ops = 15
elif R * C <= 60000:
max_ops = 12
else:
max_ops = 10
while queue:
white_cells_frozen, ops = queue.popleft()
white_cells = set(white_cells_frozen)
if ops >= max_ops:
continue
# Try each possible stamp operation
for a, b in stamp_positions:
new_white = apply_stamp(white_cells, a, b)
# Check if this creates a path
if has_path(new_white):
return ops + 1
# Add to queue if not seen before and promising
new_config = frozenset(new_white)
if new_config not in visited_configs and len(visited_configs) < 100000:
visited_configs.add(new_config)
queue.append((new_config, ops + 1))
return -1 # Should not happen given constraints
```
# Read and solve
result = solve()
print(result)