結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-20 17:54:56 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,021 bytes |
コンパイル時間 | 521 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2025-04-20 17:54:58 |
合計ジャッジ時間 | 2,200 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 WA * 14 |
ソースコード
import sys from collections import deque def sieve(n): is_prime = [True]*(n+1) is_prime[0]=is_prime[1]=False for i in range(2,int(n**0.5)+1): if is_prime[i]: for j in range(i*i, n+1, i): is_prime[j]=False return [i for i,pr in enumerate(is_prime) if pr], is_prime def min_prime_pair_sum(delta, primes, is_prime): INF = 10**9 best = INF for pB in primes: pA = pB + delta if pA < 2: continue if pA < len(is_prime) and is_prime[pA]: best = min(best, pA + pB) return best if best < INF else None def main(): input = sys.stdin.readline 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()) grid = [list(input().rstrip()) for _ in range(H)] q = deque([(Sx,Sy)]) vis = [[False]*W for _ in range(H)] vis[Sx][Sy]=True dr = [1,-1,0,0] dc = [0,0,1,-1] has_vert = False has_horiz = False while q: r,c = q.popleft() for nr,nc in [(r+1,c),(r-1,c)]: if 0<=nr<H and 0<=nc<W and grid[nr][nc] != '#' and vis[nr][nc]: has_vert = True for nr,nc in [(r,c+1),(r,c-1)]: if 0<=nr<H and 0<=nc<W and grid[nr][nc] != '#' and vis[nr][nc]: has_horiz = True for d in range(4): nr, nc = r+dr[d], c+dc[d] if 0<=nr<H and 0<=nc<W and not vis[nr][nc] and grid[nr][nc] != '#': vis[nr][nc]=True q.append((nr,nc)) if not vis[Gx][Gy]: print(-1) return primes, is_prime = sieve(5000) dx = Gx - Sx dy = Gy - Sy if not has_vert: print(-1); return if not has_horiz: print(-1); return vx = min_prime_pair_sum(dx, primes, is_prime) vy = min_prime_pair_sum(dy, primes, is_prime) if vx is None or vy is None: print(-1) else: print(vx + vy) if __name__ == "__main__": main()