結果
| 問題 |
No.323 yuki国
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:58 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,835 ms / 5,000 ms |
| コード長 | 6,302 bytes |
| コンパイル時間 | 196 ms |
| コンパイル使用メモリ | 81,920 KB |
| 実行使用メモリ | 180,480 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:52 |
| 合計ジャッジ時間 | 11,261 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 6 |
| other | AC * 32 |
ソースコード
import sys
import collections
# Use sys.stdin.readline for faster input reading, as recommended for competitive programming
input = sys.stdin.readline
def solve():
# Read grid dimensions H (height/rows) and W (width/columns)
H, W = map(int, input().split())
# Read initial state: A (initial size), Si, Sj (start row, col)
A, Si, Sj = map(int, input().split())
# Read target state: B (target size), Gi, Gj (goal row, col)
B, Gi, Gj = map(int, input().split())
# Read the grid map M, where '*' denotes snow and '.' denotes no snow
M = [input().strip() for _ in range(H)]
# Parity Check:
# When moving to an adjacent cell (i', j') from (i, j), the parity of i+j changes.
# If the destination cell has snow ('*'), size s becomes s+1. Parity of s changes if s is even, stays if s is odd. Incorrect: parity changes if s+1 has different parity than s, which is always true.
# If the destination cell has no snow ('.') size s becomes s-1. Parity of s changes.
# Let's analyze the parity of (row + col + size).
# Move from (i, j, s) to (i', j', s').
# Parity of i'+j' is different from parity of i+j.
# Parity of s' is different from parity of s (since s' = s+1 or s-1).
# Therefore, parity of (i'+j') + s' is the SAME as parity of (i+j) + s.
# (Different + Different = Same parity overall)
# This means the parity of (row + col + size) must be invariant throughout any path.
# Check if the start state parity matches the target state parity.
start_parity = (Si + Sj + A) % 2
target_parity = (Gi + Gj + B) % 2
if start_parity != target_parity:
# If parities don't match, it's impossible to reach the target state.
print('No')
return
# Determine the maximum snowball size to keep track of in the state space.
# Any path from start S to goal G must consist of some number of steps k.
# The size changes by k_snow - k_nosnow. Max size increase is k, max decrease is k.
# A simple path (no repeated cells) has length k <= H*W.
# If we reach a state (r, c, s) where s > B + H*W, any simple path from (r,c) to (G_i, G_j)
# will end with size > B. To reach size B, a path with cycles is needed to decrease size significantly.
# A reasonably safe upper bound for the necessary size seems to be max(A, B) + H * W.
# We track states with size up to this maximum value. S_limit is 1 + this maximum value.
# Sizes tracked are in the range [1, S_limit-1].
S_max_tracked = max(A, B) + H * W
S_limit = S_max_tracked + 1
# Initial state validity check
# The problem constraints state 1 <= A, B <= 1000. So A is always >= 1.
# Also, A <= 1000. The maximum value of S_max_tracked is 1000 + 50*50 = 3500.
# S_limit is 3501. So A is always less than S_limit. No check needed for A >= S_limit initially.
# Initialize BFS queue
q = collections.deque()
# Visited array to keep track of visited states (row, col, size).
# Using a 3D list for performance. Dimensions: H x W x S_limit.
# Memory check: H*W*S_limit*sizeof(bool) <= 50*50*3501 * ~24 bytes (python bool object) ~= 210 MB. This should be okay for 512 MB limit.
# If memory limit is tight, could use bytearray or dictionary.
try:
# Attempt to allocate memory for the visited array.
visited = [[[False] * S_limit for _ in range(W)] for _ in range(H)]
except MemoryError:
# This error might occur if S_limit is unexpectedly large or system memory is low.
sys.stderr.write("Memory allocation failed. The state space might be too large.\n")
# In a contest setting, this could lead to Memory Limit Exceeded.
# Depending on the platform/rules, might need to exit or handle differently.
# Using a dictionary `visited = {}` with keys `(r, c, s)` is an alternative,
# potentially slower access but uses memory proportional to reachable states.
# For now, we assume the list allocation succeeds based on estimates.
exit(1) # Exit if memory allocation fails.
# Add the initial state to the queue and mark it as visited.
q.append((Si, Sj, A))
visited[Si][Sj][A] = True
# Define the 4 possible directions (Up, Down, Left, Right)
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
found = False # Flag to indicate if the target state has been reached
# Start the Breadth-First Search
while q:
# Dequeue the next state to explore
r, c, s = q.popleft()
# Check if the current state is the target state
if r == Gi and c == Gj and s == B:
found = True
break # Target found, terminate BFS
# Explore neighbors of the current cell (r, c)
for i in range(4):
nr, nc = r + dr[i], c + dc[i] # Calculate neighbor coordinates
# Check if the neighbor cell (nr, nc) is within the grid boundaries
if 0 <= nr < H and 0 <= nc < W:
# Calculate the new snowball size after moving to the neighbor cell
# Size increases by 1 if the cell has snow ('*'), decreases by 1 otherwise ('.')
new_s = s + 1 if M[nr][nc] == '*' else s - 1
# Check if the new state is valid:
# 1. Snowball size must be at least 1 (it hasn't melted).
# 2. Snowball size must be less than S_limit (within the tracked range). Pruning states with large sizes.
if 1 <= new_s < S_limit:
# Check if this state (nr, nc, new_s) has been visited before
if not visited[nr][nc][new_s]:
# If not visited, mark it as visited
visited[nr][nc][new_s] = True
# Add the new state to the queue for exploration
q.append((nr, nc, new_s))
# Implicit else: if new_s < 1 (melted) or new_s >= S_limit (too large),
# this path is invalid/pruned, so we don't add it to the queue.
# After the BFS completes (queue is empty or target found):
# Print the result based on whether the target state was reached.
if found:
print('Yes')
else:
print('No')
# Execute the main solve function
solve()