結果

問題 No.3121 Prime Dance
ユーザー Nzt3
提出日時 2025-03-27 16:11:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,389 bytes
コンパイル時間 3,563 ms
コンパイル使用メモリ 293,972 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-08 23:39:25
合計ジャッジ時間 4,431 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto&& e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S>
bool chmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
bool chmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

int main() {
  int H, W;
  cin >> H >> W;
  array<int, 2> S, G;
  cin >> S[0] >> S[1];
  cin >> G[0] >> G[1];
  --S[0], --S[1];
  --G[0], --G[1];
  vector<string> C(H);
  fore(i, C) cin >> i;
  int ans = 1e9;
  using ai4 = array<int, 4>;
  const int MAX_P = 100000;
  vector prime(MAX_P, 1);
  prime[0] = prime[1] = 0;
  for (ll i = 2; i < MAX_P; i++) {
    if (!prime[i]) continue;
    for (ll j = i * i; j < MAX_P; j += i) prime[j] = 0;
  }
  auto move_ok = [&](int x, int y) {
    if (x < 0 || x >= H || y < 0 || y >= W) return false;
    return C[x][y] != '#';
  };
  int dx[] = {0, 1, 0, -1};
  int dy[] = {-1, 0, 1, 0};
  {
    // ab min
    auto comp = [](const ai4& a, const ai4& b) { return a[0] > b[0]; };
    vector dist(H, vector(W, (int)1e9));
    dist[S[0]][S[1]] = 0;
    priority_queue<ai4, vector<ai4>, decltype(comp)> pq(comp);
    pq.push(ai4{0, 0, S[0], S[1]});
    while (pq.size()) {
      auto [a, c, x, y] = pq.top();
      pq.pop();
      if (dist[x][y] != a) continue;
      if (x == G[0] && y == G[1]) {
        // Goal
        // cerr << "a: " << a << " c:" << c << endl;
        int h = 1e9, w = 1e9;
        for (int i = a; i < MAX_P; i++) {
          int b = i - (G[0] - S[0]);
          if (b >= 0 && b < MAX_P && prime[b] & prime[i]) {
            h = i + b;
            break;
          }
        }
        for (int i = c; i < MAX_P; i++) {
          int d = i - (G[1] - S[1]);
          if (d >= 0 && d < MAX_P && prime[d] & prime[i]) {
            w = i + d;
            break;
          }
        }
        chmin(ans, h + w);
        break;
      }
      rep(i, 4) {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (move_ok(x2, y2) && dist[x2][y2] > a + (i == 1)) {
          dist[x2][y2] = a + (i == 1);
          pq.push(ai4{a + (i == 1), c + (i == 2), x2, y2});
        }
      }
    }
  }
  {
    // cd min
    auto comp = [](const ai4& a, const ai4& b) { return a[1] > b[1]; };
    vector dist(H, vector(W, (int)1e9));
    dist[S[0]][S[1]] = 0;
    priority_queue<ai4, vector<ai4>, decltype(comp)> pq(comp);
    pq.push(ai4{0, 0, S[0], S[1]});
    while (pq.size()) {
      auto [a, c, x, y] = pq.top();
      pq.pop();
      if (dist[x][y] != c) continue;
      if (x == G[0] && y == G[1]) {
        // Goal
        // cerr << "a: " << a << " c:" << c << endl;
        int h = 1e9, w = 1e9;
        for (int i = a; i < MAX_P; i++) {
          int b = i - (G[0] - S[0]);
          if (b >= 0 && b < MAX_P && prime[b] & prime[i]) {
            h = i + b;
            break;
          }
        }
        for (int i = c; i < MAX_P; i++) {
          int d = i - (G[1] - S[1]);
          if (d >= 0 && d < MAX_P && prime[d] & prime[i]) {
            w = i + d;
            break;
          }
        }
        chmin(ans, h + w);
        break;
      }
      rep(i, 4) {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (move_ok(x2, y2) && dist[x2][y2] > c + (i == 2)) {
          dist[x2][y2] = c + (i == 2);
          pq.push(ai4{a + (i == 1), c + (i == 2), x2, y2});
        }
      }
    }
  }
  {
    // sum min
    auto comp = [](const ai4& a, const ai4& b) {
      return a[0] + a[1] > b[0] + b[1];
    };
    vector dist(H, vector(W, (int)1e9));
    dist[S[0]][S[1]] = 0;
    priority_queue<ai4, vector<ai4>, decltype(comp)> pq(comp);
    pq.push(ai4{0, 0, S[0], S[1]});
    while (pq.size()) {
      auto [a, c, x, y] = pq.top();
      pq.pop();
      if (dist[x][y] != a + c) continue;
      if (x == G[0] && y == G[1]) {
        // Goal
        // cerr << "a: " << a << " c:" << c << endl;
        int h = 1e9, w = 1e9;
        for (int i = a; i < MAX_P; i++) {
          int b = i - (G[0] - S[0]);
          if (b >= 0 && b < MAX_P && prime[b] & prime[i]) {
            h = i + b;
            break;
          }
        }
        for (int i = c; i < MAX_P; i++) {
          int d = i - (G[1] - S[1]);
          if (d >= 0 && d < MAX_P && prime[d] & prime[i]) {
            w = i + d;
            break;
          }
        }
        chmin(ans, h + w);
        break;
      }
      rep(i, 4) {
        int x2 = x + dx[i], y2 = y + dy[i];
        if (move_ok(x2, y2) && dist[x2][y2] > a + c + (i == 1) + (i == 2)) {
          dist[x2][y2] = a + c + (i == 1) + (i == 2);
          pq.push(ai4{a + (i == 1), c + (i == 2), x2, y2});
        }
      }
    }
  }
  cout << (ans == 1e9 ? -1 : ans) << '\n';
}
0