結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-24 15:52:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,938 bytes |
コンパイル時間 | 2,353 ms |
コンパイル使用メモリ | 209,460 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-24 15:52:46 |
合計ジャッジ時間 | 3,314 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 WA * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H,W,Sx,Sy,Gx,Gy; cin >> H >> W >> Sx >> Sy >> Gx >> Gy; vector<string> C(H); for(int i=0;i<H;i++) cin >> C[i]; // 1) BFS で到達可能性チェック vector dist(H, vector<int>(W, -1)); queue<pair<int,int>> q; dist[Sx-1][Sy-1] = 0; q.emplace(Sx-1, Sy-1); 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]=='#') continue; if(dist[nx][ny]==-1){ dist[nx][ny] = dist[x][y] + 1; q.emplace(nx, ny); } } } if(dist[Gx-1][Gy-1] == -1){ cout << -1; return 0; } // 2) 素数列挙(上限は十分余裕を持って200まで) const int LIM = 200; vector<bool> is_prime(LIM+1, true); is_prime[0]=is_prime[1]=false; for(int i=2;i*i<=LIM;i++) if(is_prime[i]){ for(int j=i*i;j<=LIM;j+=i) is_prime[j]=false; } vector<int> primes; for(int i=2;i<=LIM;i++) if(is_prime[i]) primes.push_back(i); int dx = abs(Gx - Sx); int dy = abs(Gy - Sy); // 3) (A,B) で A-B = dx を満たすものの最小 A+B ll bestV = LLONG_MAX; for(int p: primes) for(int q: primes){ if(p - q == dx){ bestV = min(bestV, ll(p) + ll(q)); } } // 4) (C,D) で C-D = dy を満たすものの最小 C+D ll bestH = LLONG_MAX; for(int p: primes) for(int q: primes){ if(p - q == dy){ bestH = min(bestH, ll(p) + ll(q)); } } if(bestV==LLONG_MAX || bestH==LLONG_MAX){ cout << -1; } else { cout << (bestV + bestH); } return 0; }