結果
| 問題 | No.3121 Prime Dance |
| ユーザー |
 shibh308
|
| 提出日時 | 2025-04-20 05:09:08 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
AC
|
| 実行時間 | 96 ms / 2,000 ms |
| コード長 | 6,194 bytes |
| コンパイル時間 | 326 ms |
| コンパイル使用メモリ | 13,312 KB |
| 実行使用メモリ | 13,440 KB |
| 最終ジャッジ日時 | 2025-04-20 05:09:12 |
| 合計ジャッジ時間 | 2,845 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 21 |
ソースコード
from heapq import heappush, heappop
from collections import deque
def solve():
H,W = map(int,input().split())
sx,sy = map(lambda x:int(x)-1, input().split())
gx,gy = map(lambda x:int(x)-1, input().split())
A = [list(input().rstrip()) for _ in range(H)]
dx = gx - sx
dy = gy - sy
vis = [[False]*W for _ in range(H)]
dq = deque([(sx,sy)])
vis[sx][sy] = True
while dq:
x,y = dq.popleft()
for dxx,dyy in ((1,0),(-1,0),(0,1),(0,-1)):
nx,ny = x+dxx, y+dyy
if 0<=nx<H and 0<=ny<W and not vis[nx][ny] and A[nx][ny] != '#':
vis[nx][ny] = True
dq.append((nx,ny))
if not vis[gx][gy]:
print(-1)
return
pareto = [[[] for _ in range(W)] for __ in range(H)]
pq = [(0,0,0,sx,sy)]
pareto[sx][sy].append((0,0))
while pq:
_, v, h, x, y = heappop(pq)
dominated = False
for vv,hh in pareto[x][y]:
if vv<=v and hh<=h and (vv,hh)!=(v,h):
dominated = True; break
if dominated: continue
for dxx,dyy in ((1,0),(-1,0),(0,1),(0,-1)):
nx,ny = x+dxx, y+dyy
if not (0<=nx<H and 0<=ny<W and A[nx][ny] != '#'): continue
nv, nh = v + (1 if dxx!=0 else 0), h + (1 if dyy!=0 else 0)
skip = False
remove = []
for idx,(vv,hh) in enumerate(pareto[nx][ny]):
if vv<=nv and hh<=nh:
skip = True; break
if nv<=vv and nh<=hh:
remove.append(idx)
if skip: continue
for idx in reversed(remove):
pareto[nx][ny].pop(idx)
pareto[nx][ny].append((nv,nh))
heappush(pq, (nv+nh, nv, nh, nx, ny))
MAXP = 200000
is_prime = [True]*(MAXP+1)
is_prime[0]=is_prime[1]=False
for i in range(2,MAXP+1):
if is_prime[i]:
for j in range(i+i, MAXP+1, i):
is_prime[j] = False
def min_pad(big, small):
for t in range(0, MAXP-big+1):
if big == 0 and t != 0:
break
p = big + t
q = small + t
if q<2: continue
if is_prime[p] and is_prime[q]:
return t
return None
ans = None
for V_,H_ in pareto[gx][gy]:
A0 = (V_ + dx)//2
B0 = (V_ - dx)//2
C0 = (H_ + dy)//2
D0 = (H_ - dy)//2
pad_v = min_pad(max(A0,B0), min(A0,B0))
pad_h = min_pad(max(C0,D0), min(C0,D0))
if pad_v is None or pad_h is None:
continue
total = (V_+H_) + 2*pad_v + 2*pad_h
if ans is None or total<ans:
ans = total
dist0 = [[-1]*W for _ in range(H)]
parent = [[None]*W for _ in range(H)]
dq2 = deque([(sx,sy)])
dist0[sx][sy] = 0
while dq2:
x,y = dq2.popleft()
for dx_,dy_,op in ((1,0,'A'),(-1,0,'B'),(0,1,'C'),(0,-1,'D')):
nx,ny = x+dx_, y+dy_
if 0<=nx<H and 0<=ny<W and A[nx][ny] != '#' and dist0[nx][ny] < 0:
dist0[nx][ny] = dist0[x][y] + 1
parent[nx][ny] = (x,y,op)
dq2.append((nx,ny))
A1=B1=C1=D1 = 0
path = []
cx,cy = gx,gy
while (cx,cy) != (sx,sy):
path.append((cx,cy))
px,py,op = parent[cx][cy]
if op=='A': A1 += 1
elif op=='B': B1 += 1
elif op=='C': C1 += 1
else: D1 += 1
cx,cy = px,py
path.append((sx,sy))
if not ( (A1+B1>0) and (C1+D1>0) ):
d2 = [[-1]*W for _ in range(H)]
dq3 = deque(path)
for x,y in path:
d2[x][y] = 0
while dq3:
x,y = dq3.popleft()
for dx_,dy_ in ((1,0),(-1,0),(0,1),(0,-1)):
nx,ny = x+dx_, y+dy_
if 0<=nx<H and 0<=ny<W and A[nx][ny] != '#' and d2[nx][ny]<0:
d2[nx][ny] = d2[x][y] + 1
dq3.append((nx,ny))
# 5) 縦移動ペア＆横移動ペアまでの最小距離を探す
INF = 10**9
best_v = INF
for i in range(H-1):
for j in range(W):
if A[i][j] != '#' and A[i+1][j] != '#':
# path→(i,j) or (i+1,j) の距離
for (ii,jj) in ((i,j),(i+1,j)):
if d2[ii][jj]>=0:
best_v = min(best_v, d2[ii][jj])
best_h = INF
for i in range(H):
for j in range(W-1):
if A[i][j] != '#' and A[i][j+1] != '#':
for (ii,jj) in ((i,j),(i,j+1)):
if d2[ii][jj]>=0:
best_h = min(best_h, d2[ii][jj])
base0 = A1 + B1 + C1 + D1 # 最短路長
extra = 0
# 縦移動ゼロならループ寄り道
if A1+B1 == 0:
if best_v < INF:
C1 += best_v
D1 += best_v
extra += 2*best_v + 4
else:
extra = INF
# 横移動ゼロならループ寄り道
if C1+D1 == 0:
if best_h < INF:
A1 += best_h
B1 += best_h
extra += 2*best_h + 4
else:
extra = INF
# ── ここから素数パディング追加 ──
if extra < INF:
# 縦移動のパディング
if A1+B1 == 0:
# 2往復して A'=B'=2 なので、2は素数→パディング不要
pad_v_exc = 0
else:
pad_v_exc = min_pad(max(A1,B1), min(A1,B1))
# 横移動のパディング
if C1+D1 == 0:
pad_h_exc = 0
else:
pad_h_exc = min_pad(max(C1,D1), min(C1,D1))
# 両方 None でないことを確認してマージ
if pad_v_exc is not None and pad_h_exc is not None:
cand = base0 + extra + 2*pad_v_exc + 2*pad_h_exc
ans = cand if ans is None else min(ans, cand)
# ── ここまで素数パディング追加 ──
print(ans if ans is not None else -1)
solve()
"""
2 3
2 2
2 3
.##
.SG
"""