結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-24 15:22:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,428 bytes |
コンパイル時間 | 2,852 ms |
コンパイル使用メモリ | 217,424 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-24 15:22:35 |
合計ジャッジ時間 | 3,957 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 WA * 13 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; int Sx, Sy, Gx, Gy; cin >> H >> W; cin >> Sx >> Sy >> Gx >> Gy; vector<string> C(H); for(int i = 0; i < H; i++) { cin >> C[i]; } // 1) BFS で最短距離 L0 を求める vector<vector<int>> dist(H, vector<int>(W, -1)); queue<pair<int,int>> q; dist[Sx-1][Sy-1] = 0; q.emplace(Sx-1, Sy-1); const int dx4[4] = {1,-1,0,0}, dy4[4] = {0,0,1,-1}; while(!q.empty()){ auto [x,y] = q.front(); q.pop(); for(int d = 0; d < 4; d++){ int nx = x + dx4[d], ny = y + dy4[d]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if(C[nx][ny] == '#' || dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } int L0 = dist[Gx-1][Gy-1]; if(L0 < 0){ cout << -1 << "\n"; return 0; } // 2) 到達可能な成分全体をマーク vector<vector<bool>> vis(H, vector<bool>(W, false)); for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(dist[i][j] >= 0) vis[i][j] = true; } } // 3) Δx, Δy の絶対値 int dx = Gx - Sx; int dy = Gy - Sy; int dv = abs(dx); int dh = abs(dy); // 4) 成分内に隣接する縦エッジ・横エッジがあるか bool adjV = false, adjH = false; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(!vis[i][j]) continue; if(i + 1 < H && vis[i+1][j]) adjV = true; if(j + 1 < W && vis[i][j+1]) adjH = true; } } // ネット移動が 0 の方向でもループ挿入には隣接エッジ必須 if(dv == 0 && !adjV){ cout << -1 << "\n"; return 0; } if(dh == 0 && !adjH){ cout << -1 << "\n"; return 0; } // 5) 素数列挙 int Np = max(L0 + dv + dh + 10, 3); vector<bool> isP(Np+1, true); isP[0] = isP[1] = false; for(int i = 2; i * i <= Np; i++){ if(isP[i]){ for(int j = i * i; j <= Np; j += i) isP[j] = false; } } vector<int> primes; for(int i = 2; i <= Np; i++){ if(isP[i]) primes.push_back(i); } // 6) 縦方向の素数ペア (差 = dv) の合計を集める vector<int> sumV; for(int p_small : primes){ int p_big = p_small + dv; if(p_big <= Np && isP[p_big]){ sumV.push_back(p_small + p_big); } } // 横方向 vector<int> sumH; for(int p_small : primes){ int p_big = p_small + dh; if(p_big <= Np && isP[p_big]){ sumH.push_back(p_small + p_big); } } if(sumV.empty() || sumH.empty()){ cout << -1 << "\n"; return 0; } sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); // ループ不可方向は最小 1 要素だけで十分 if(!adjV) sumV.resize(1); if(!adjH) sumH.resize(1); // 7) 二分探索で最小合計 >= L0 を求める int ans = INT_MAX; for(int v : sumV){ int need = L0 - v; auto it = lower_bound(sumH.begin(), sumH.end(), need); if(it != sumH.end()){ ans = min(ans, v + *it); } } if(ans == INT_MAX) ans = -1; cout << ans << "\n"; return 0; }