結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-24 15:53:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,900 bytes |
コンパイル時間 | 2,807 ms |
コンパイル使用メモリ | 216,116 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-24 15:53:10 |
合計ジャッジ時間 | 3,825 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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) 最短距離 L0 を BFS で 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 の絶対値 dv,dh int dx = Gx - Sx, dy = Gy - Sy; int dv = abs(dx), 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; } // ループ(往復)ができないなら impossible if(dv == 0 && !adjV){ cout<<-1<<"\n"; return 0; } if(dh == 0 && !adjH){ cout<<-1<<"\n"; return 0; } // 5) 素数列挙 up to Np 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 : primes){ int q = p + dv; // ここを dx ではなく dv で if(q <= Np && isP[q]) sumV.push_back(p + q); } // 横方向ペア (差 = dh) vector<int> sumH; for(int p : primes){ int q = p + dh; // ここも dh if(q <= Np && isP[q]) sumH.push_back(p + q); } if(sumV.empty() || sumH.empty()){ cout << -1 << "\n"; return 0; } sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); // 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; }