結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-24 15:17:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,862 bytes |
コンパイル時間 | 3,062 ms |
コンパイル使用メモリ | 221,852 KB |
実行使用メモリ | 15,760 KB |
最終ジャッジ日時 | 2025-04-24 15:17:20 |
合計ジャッジ時間 | 16,401 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct P { int x,y,a,c; }; 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]; int dx = Gx - Sx, dy = Gy - Sy; // 1) 素数列挙 const int MAXP = 100; vector<bool> is_p(MAXP+1,true); is_p[0]=is_p[1]=false; for(int i=2;i*i<=MAXP;i++) if(is_p[i]) for(int j=i*i;j<=MAXP;j+=i) is_p[j]=false; vector<int> primes; for(int i=2;i<=MAXP;i++) if(is_p[i]) primes.push_back(i); // 2)(A,B) ペア vector<pair<int,int>> AB; for(int A:primes) for(int B:primes){ if(A - B == dx) AB.emplace_back(A,B); } // 3)(C,D) ペア vector<pair<int,int>> CD; for(int C_:primes) for(int D:primes){ if(C_ - D == dy) CD.emplace_back(C_,D); } if(AB.empty() || CD.empty()){ cout << -1; return 0; } // 4) 全組合せを (S, A,B,C,D) でソート struct Q{int S,A,B,C,D;}; vector<Q> cand; for(auto [A,B]:AB) for(auto [C_,D]:CD){ cand.push_back({A+B+C_+D, A,B,C_,D}); } sort(cand.begin(), cand.end(), [](auto &l, auto&r){return l.S<r.S;}); // 5) 各候補で BFS 存在判定 auto inb = [&](int x,int y){ return x>=1 && x<=H && y>=1 && y<=W && C[x-1][y-1] != '#'; }; for(auto &q: cand){ int A=q.A, B=q.B, Cc=q.C, D=q.D; // visited[x][y][a][c] // 動的に確保 vector vis(H+1, vector(W+1, vector(A+1, vector<bool>(Cc+1,false)) )); queue<P> que; vis[Sx][Sy][0][0] = true; que.push({Sx,Sy,0,0}); bool ok=false; while(!que.empty() && !ok){ auto [x,y,a,c] = que.front(); que.pop(); // 到達判定 if(x==Gx && y==Gy && a==A && c==Cc){ ok = true; break; } // 4 方向 static const int dx4[4]={1,-1,0,0}; static const int dy4[4]={0,0,1,-1}; for(int d=0;d<4;d++){ int nx=x+dx4[d], ny=y+dy4[d]; if(!inb(nx,ny)) continue; int na = a + (d==0); int nc = c + (d==2); if(na> A || nc> Cc) continue; // b = na - (nx-Sx), dcnt = nc - (ny-Sy) int bcnt = na - (nx - Sx); int dcnt = nc - (ny - Sy); if(bcnt<0 || bcnt> B) continue; if(dcnt<0 || dcnt> D) continue; if(!vis[nx][ny][na][nc]){ vis[nx][ny][na][nc] = true; que.push({nx,ny,na,nc}); } } } if(ok){ cout << q.S; return 0; } } // 6) 全滅 cout << -1; return 0; }