結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-24 15:18:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,871 bytes |
コンパイル時間 | 2,904 ms |
コンパイル使用メモリ | 216,532 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-24 15:18:25 |
合計ジャッジ時間 | 3,878 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(NULL); 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)); deque<pair<int,int>> dq; dist[Sx-1][Sy-1] = 0; dq.emplace_back(Sx-1, Sy-1); int dx4[4] = {1,-1,0,0}, dy4[4] = {0,0,1,-1}; while(!dq.empty()){ auto [x,y] = dq.front(); dq.pop_front(); 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; dq.emplace_back(nx,ny); } } int L0 = dist[Gx-1][Gy-1]; if(L0<0){ cout << -1; return 0; } // 成分内到達マーク 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; // 2) Δx,Δy の計算 int dx = Gx - Sx; int dy = Gy - Sy; // 3) 隣接セルの有無 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; } if(dx==0 && !adjV){ cout<<-1; return 0; } if(dy==0 && !adjH){ cout<<-1; return 0; } // 4) 素数列挙(Eratosthenes) int Np = L0 + abs(dx) + abs(dy) + 10; Np = max(Np, 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); // (Δx)方向のペア vector<int> sumV; for(int p2: primes){ int p1 = p2 + dx; if(p1>=2 && p1<=Np && isP[p1]){ sumV.push_back(p1 + p2); } } // (Δy)方向 vector<int> sumH; for(int p2: primes){ int p1 = p2 + dy; if(p1>=2 && p1<=Np && isP[p1]){ sumH.push_back(p1 + p2); } } if(sumV.empty() || sumH.empty()){ cout<<-1; return 0; } sort(sumV.begin(), sumV.end()); sort(sumH.begin(), sumH.end()); // ループ不可方向はベース1つに制限 if(!adjV) sumV.resize(1); if(!adjH) sumH.resize(1); // 5) 最小合計和 >= L0 を二分探索で int ans = INT_MAX; for(int vx: sumV){ int need = L0 - vx; auto it = lower_bound(sumH.begin(), sumH.end(), need); if(it!=sumH.end()){ ans = min(ans, vx + *it); } } if(ans==INT_MAX) ans = -1; cout << ans; return 0; }