結果

問題 No.308 素数は通れません
ユーザー gew1fw
提出日時 2025-06-12 20:32:22
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,488 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 82,836 KB
実行使用メモリ 269,600 KB
最終ジャッジ日時 2025-06-12 20:33:39
合計ジャッジ時間 7,263 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 56 MLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def is_valid_path(W, N):
    def get_position(x):
        return (x // W, x % W)
    
    start = 1
    end = N
    if start == end:
        return True
    
    visited = set()
    queue = [(get_position(start - 1), [start])]
    
    while queue:
        (x, y), path = queue.pop(0)
        if (x, y) == get_position(end - 1):
            return True
        
        current = path[-1]
        if current == end:
            return True
        
        neighbors = []
        if x > 0:
            neighbors.append((x - 1, y))
        if x < (N - 1) // W:
            neighbors.append((x + 1, y))
        if y > 0:
            neighbors.append((x, y - 1))
        if y < W - 1:
            neighbors.append((x, y + 1))
        
        for nx, ny in neighbors:
            num = nx * W + ny + 1
            if num > N:
                continue
            if not is_prime(num) and num not in visited:
                visited.add(num)
                new_path = path + [num]
                queue.append(((nx, ny), new_path))
    
    return False

def find_min_w(N):
    if N == 4:
        return 3
    for W in range(1, N):
        if (W >= N - 1) or is_valid_path(W, N):
            return W
    return N - 1

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    print(find_min_w(N))
0