結果
問題 |
No.3121 Prime Dance
|
ユーザー |
|
提出日時 | 2025-04-20 16:44:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,792 bytes |
コンパイル時間 | 2,462 ms |
コンパイル使用メモリ | 210,504 KB |
実行使用メモリ | 144,928 KB |
最終ジャッジ日時 | 2025-04-20 16:44:26 |
合計ジャッジ時間 | 9,657 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 2 |
other | AC * 8 WA * 2 TLE * 1 -- * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MAX = 40; const int INF = 1e9; int H, W; int Sx, Sy, Gx, Gy; char grid[MAX][MAX]; struct State { int x, y; int a, b, c, d; }; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int main() { vector<bool>sosu(20001,true); sosu[0] = false; sosu[1] = false; for(int i = 2;i<450;i++){ if(sosu[i] != true)continue; else{ long long j = 2; while(j*i < 20001){ sosu[j*i] = false; j++; } } } cin >> H >> W; cin >> Sx >> Sy; cin >> Gx >> Gy; Sx--; Sy--; Gx--; Gy--; for (int i = 0; i < H; ++i) { cin >> grid[i]; } queue<State> q; set<tuple<int, int, int, int, int, int>> visited; q.push({Sx, Sy, 0, 0, 0, 0}); visited.insert({Sx, Sy, 0, 0, 0, 0}); int ans = INF; while (!q.empty()) { State s = q.front(); q.pop(); if (s.x == Gx && s.y == Gy) { if (sosu[s.a] && sosu[s.b] && sosu[s.c] && sosu[s.d]) { ans = min(ans, s.a + s.b + s.c + s.d); } } for (int dir = 0; dir < 4; ++dir) { int nx = s.x + dx[dir]; int ny = s.y + dy[dir]; if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if (grid[nx][ny] == '#') continue; int na = s.a + (dir == 0); int nb = s.b + (dir == 1); int nc = s.c + (dir == 2); int nd = s.d + (dir == 3); if (na > 150 || nb > 150 || nc > 150 || nd > 150) continue; auto state = make_tuple(nx, ny, na, nb, nc, nd); if (visited.count(state)) continue; visited.insert(state); q.push({nx, ny, na, nb, nc, nd}); } } cout << (ans == INF ? -1 : ans) << endl; return 0; }