結果

問題 No.3121 Prime Dance
ユーザー karashi-0086A2
提出日時 2025-04-20 19:36:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,055 bytes
コンパイル時間 1,547 ms
コンパイル使用メモリ 107,292 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-20 19:36:12
合計ジャッジ時間 2,732 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

// 素数を求める関数 (エラトステネスの篩)
vector<int> sieve(int limit) {
    vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

struct State {
    int x, y, A, B, C, D;
};

int bfs(int H, int W, const vector<string>& grid, pair<int, int> start, pair<int, int> goal, const vector<int>& primes) {
    // 4方向の移動 (右, 左, 下, 上)
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    // 最小移動回数を格納する配列
    vector<vector<vector<bool>>> visited(H, vector<vector<bool>>(W, vector<bool>(primes.size(), false)));
    
    // BFS のキュー (x, y, A, B, C, D の移動回数)
    queue<State> q;
    q.push({start.first, start.second, 0, 0, 0, 0});
    visited[start.first][start.second][0] = true;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        // ゴールに到達したら操作回数の合計を返す
        if (current.x == goal.first && current.y == goal.second) {
            return current.A + current.B + current.C + current.D;
        }

        // 4方向に対して素数回の移動を試す
        for (auto& dir : directions) {
            int nx = current.x + dir.first;
            int ny = current.y + dir.second;

            if (nx >= 0 && nx < H && ny >= 0 && ny < W && grid[nx][ny] != '#') {
                // 各方向に対して素数回の移動を試みる
                for (int i = 0; i < primes.size(); i++) {
                    if (!visited[nx][ny][i]) {
                        visited[nx][ny][i] = true;
                        q.push({nx, ny, current.A + primes[i], current.B + primes[i], current.C + primes[i], current.D + primes[i]});
                    }
                }
            }
        }
    }

    return -1;  // ゴールに到達できなかった場合
}

int main() {
    int H, W;
    cin >> H >> W;
    
    vector<string> grid(H);
    pair<int, int> start, goal;
    
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == 'S') {
                start = {i, j};
            } else if (grid[i][j] == 'G') {
                goal = {i, j};
            }
        }
    }

    // 最大移動回数は最大で40（HとWの最大値）なので、エラトステネスの篩で素数を計算
    int max_move = max(H, W);
    vector<int> primes = sieve(max_move * 2);  // 最大で80回の移動をカバー

    // BFSによる探索
    int result = bfs(H, W, grid, start, goal, primes);
    cout << result << endl;

    return 0;
}
0