結果
問題 | No.3121 Prime Dance |
ユーザー |
|
提出日時 | 2025-05-02 19:16:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 572 ms / 2,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 3,260 ms |
コンパイル使用メモリ | 233,316 KB |
実行使用メモリ | 77,568 KB |
最終ジャッジ日時 | 2025-05-02 19:17:06 |
合計ジャッジ時間 | 11,056 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <typename T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <typename T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct IOST { IOST() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20); } } IOST; void solve() { int h, w; cin >> h >> w; int stx, sty, edx, edy; cin >> stx >> sty >> edx >> edy; stx--, sty--; edx--, edy--; vector<string> c(h); rep(i, 0, h) cin >> c[i]; int dfx = (edx - stx); int dfy = (edy - sty); int m = 160; vector dp(m + 1, vector(m + 1, vector(h, vector<bool>(w, 0)))); dp[0][0][stx][sty] = 1; rep(i, 0, m) rep(j, 0, m) { rep(x, 0, h) rep(y, 0, w) { if (dp[i][j][x][y]) { if (x + 1 < h && c[x + 1][y] != '#') dp[i][j][x + 1][y] = 1; if (y + 1 < w && c[x][y + 1] != '#') dp[i][j][x][y + 1] = 1; if (x > 0 && c[x - 1][y] != '#') dp[i + 1][j][x - 1][y] = 1; if (y > 0 && c[x][y - 1] != '#') dp[i][j + 1][x][y - 1] = 1; } } } set<int> p; { int d = 1e4; vector<int> mm(d, 0); rep(i, 2, d) { if (mm[i]) continue; for (int j = i * 2; j < d; j += i) { mm[j] = 1; } p.insert(i); } } ll ans = 1e18; rep(b, 0, m) rep(d, 0, m) { if (!p.count(b) || !p.count(d)) continue; if (dp[b][d][edx][edy]) { if (!p.count(dfx + b) || !p.count(dfy + d)) continue; chmin(ans, dfx + b + b + dfy + d + d); } } if (ans == 1e18) ans = -1; cout << ans << "\n"; } int main() { int t = 1; // cin >> t; rep(i, 0, t) solve(); }