結果

問題 No.3121 Prime Dance
ユーザー 入野拳樹
提出日時 2025-04-20 16:47:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,888 bytes
コンパイル時間 2,620 ms
コンパイル使用メモリ 210,968 KB
実行使用メモリ 146,848 KB
最終ジャッジ日時 2025-04-20 16:47:37
合計ジャッジ時間 7,434 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 10 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int H, W;
    cin >> H >> W;
    int Sx, Sy, Gx, Gy;
    cin >> Sx >> Sy >> Gx >> Gy;
    Sx--; Sy--; Gx--; Gy--;
    
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }
    
    // State: (x, y, A, B, C, D)
    using State = tuple<int, int, int, int, int, int>;
    queue<State> q;
    set<State> visited;
    
    q.push({Sx, Sy, 0, 0, 0, 0});
    visited.insert({Sx, Sy, 0, 0, 0, 0});
    
    int dx[] = {1, -1, 0, 0};  // A, B, C, D
    int dy[] = {0, 0, 1, -1};
    
    int ans = -1;
    while (!q.empty()) {
        auto [x, y, A, B, C, D] = q.front();
        q.pop();
        
        if (x == Gx && y == Gy && isPrime(A) && isPrime(B) && isPrime(C) && isPrime(D)) {
            int total = A + B + C + D;
            if (ans == -1 || total < ans) {
                ans = total;
            }
            continue;
        }
        
        for (int dir = 0; dir < 4; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            
            if (nx < 0 || nx >= H || ny < 0 || ny >= W || grid[nx][ny] == '#') continue;
            
            int nA = A + (dir == 0);
            int nB = B + (dir == 1);
            int nC = C + (dir == 2);
            int nD = D + (dir == 3);
            
            // Prune if any count exceeds reasonable prime numbers
            if (nA > 97 || nB > 97 || nC > 97 || nD > 97) continue;
            
            State newState = {nx, ny, nA, nB, nC, nD};
            if (visited.count(newState)) continue;
            
            visited.insert(newState);
            q.push(newState);
        }
    }
    
    cout << ans << endl;
    return 0;
}
0