結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-20 18:02:08 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,013 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 12,288 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2025-04-20 18:02:10 |
合計ジャッジ時間 | 1,855 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 WA * 14 |
ソースコード
import sys from collections import deque def sieve(n): is_prime = [False, False] + [True] * (n-1) 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 is_prime def find_min_prime_sum(delta, is_prime, primes): INF = 10**9 best = INF for q in primes: p = q + delta if p >= 2 and p < len(is_prime) and is_prime[p]: best = min(best, p + q) return best if best < INF else None def main(): input = sys.stdin.readline H, W = map(int, input().split()) sx, sy = map(int, input().split()) gx, gy = map(int, input().split()) sx -= 1; sy -= 1; gx -= 1; gy -= 1 grid = [list(input().rstrip()) for _ in range(H)] seen = [[False]*W for _ in range(H)] dq = deque([(sx, sy)]) seen[sx][sy] = True comp = [] while dq: x, y = dq.popleft() comp.append((x,y)) 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 not seen[nx][ny] and grid[nx][ny] != '#': seen[nx][ny] = True dq.append((nx,ny)) if not seen[gx][gy]: print(-1) return vert_ok = False hori_ok = False for x, y in comp: for dx, dy in ((1,0),(0,1)): nx, ny = x+dx, y+dy if 0 <= nx < H and 0 <= ny < W and seen[nx][ny] and grid[nx][ny] != '#': if dx != 0: vert_ok = True if dy != 0: hori_ok = True if not vert_ok or not hori_ok: print(-1) return MAXP = 500 is_prime = sieve(MAXP) primes = [i for i in range(2, MAXP+1) if is_prime[i]] dx = gx - sx dy = gy - sy row_sum = find_min_prime_sum(dx, is_prime, primes) col_sum = find_min_prime_sum(dy, is_prime, primes) if row_sum is None or col_sum is None: print(-1) else: print(row_sum + col_sum) if __name__ == "__main__": main()