結果
問題 |
No.3121 Prime Dance
|
ユーザー |
![]() |
提出日時 | 2025-04-20 19:29:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,724 bytes |
コンパイル時間 | 3,943 ms |
コンパイル使用メモリ | 300,396 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-04-20 19:29:13 |
合計ジャッジ時間 | 5,059 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 WA * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; std::vector<int> primes(const int N ) { std::vector<bool> is_prime( N + 1 ); for( int i = 0; i <= N; i++ ) { is_prime[ i ] = true; } std::vector<int> P; for( int i = 2; i <= N; i++ ) { if( is_prime[ i ] ) { for( int j = 2 * i; j <= N; j += i ) { is_prime[ j ] = false; } P.emplace_back( i ); } } return P; } auto grid_bfs(vector< string > &s, char start, int gy, int gx, const string &wall = "#") { const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0}; vector< vector< int > > min_cost(s.size(), vector< int >(s[0].size(), -1)); vector<vector<pair<int, int>>> cost(s.size(), vector<std::pair<int, int>>(s[0].size(), { -1, -1 })); queue< pair< int, int > > que; for(int i = 0; i < s.size(); i++) { for(int j = 0; j < s[i].size(); j++) { if(s[i][j] == start) { que.emplace(i, j); min_cost[i][j] = 0; cost[i][j] = { 0, 0 }; } } } while(!que.empty()) { auto p = que.front(); que.pop(); for(int i = 0; i < 4; i++) { int ny = p.first + vy[i], nx = p.second + vx[i]; if(nx < 0 || ny < 0 || nx >= s[0].size() || ny >= s.size()) continue; if(min_cost[ny][nx] != -1) continue; if(wall.find(s[ny][nx]) != string::npos) continue; min_cost[ny][nx] = min_cost[p.first][p.second] + 1; cost[ny][nx].first = cost[p.first][p.second].first + std::abs(vy[i]); cost[ny][nx].second = cost[p.first][p.second].second + std::abs(vx[i]); que.emplace(ny, nx); } } return cost[gy][gx]; } int main() { const auto ps = primes(100000); std::map<long, std::vector<int>> mp; for(int i : std::views::iota(1uz, ps.size())) { const int d = ps[i] - ps[i - 1]; mp[d].push_back(ps[i - 1]); } // for(auto& [ k, v ] : mp) { // std::cerr << "{" << k << ", {"; // for(auto x: v) std::cerr << x << ", "; // std::cerr << "} }, "; // } int h, w; std::cin >> h >> w; int sx, sy; std::cin >> sx >> sy; --sx, --sy; int gx, gy; std::cin >> gx >> gy; --gx, --gy; std::vector<std::string> grid(h); for(auto& row : grid) std::cin >> row; // std::cout << "test" << "\n"; auto p = grid_bfs(grid, 'S', gx, gy); std::cerr << p.first << ", " << p.second << "\n"; int dx = std::abs(sx - gx); int dy = std::abs(sy - gy); auto itrx = std::ranges::lower_bound(mp[dx], p.first); auto itry = std::ranges::lower_bound(mp[dy], p.second); if(itrx == mp[dx].end() || itry == mp[dy].end()) { std::cout << "-1\n"; return 0; } std::cerr << *itrx << ", " << *itry << "\n"; std::cout << 2 * (*itrx + *itry) + dx + dy << "\n"; }