結果

問題 No.3121 Prime Dance
コンテスト
ユーザー Nzt3
提出日時 2025-03-24 16:59:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,578 bytes
コンパイル時間 3,577 ms
コンパイル使用メモリ 294,960 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-08 23:39:27
合計ジャッジ時間 6,549 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:127:36: warning: narrowing conversion of ‘k’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
  127 |             pq.push(ai4{d, x2, y2, k});
      |                                    ^

ソースコード

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); }
} __;

const int MAX_P = 100000;

int main() {
  int H, W;
  cin >> H >> W;
  using ai2 = array<int, 2>;
  ai2 S, G;
  cin >> S[0] >> S[1];
  --S[0], --S[1];
  cin >> G[0] >> G[1];
  --G[0], --G[1];
  vector<string> C(H);
  rep(i, H) cin >> C[i];
  if (S[0] > G[0]) {
    S[0] = H - 1 - S[0], G[0] = H - 1 - G[0];
    reverse(all(C));
  }
  if (S[1] > G[1]) {
    S[1] = W - 1 - S[1], G[1] = W - 1 - G[1];
    fore(i, C) reverse(all(i));
  }
  vector p(MAX_P, true);
  p[0] = p[1] = 0;
  rep(i, 2, MAX_P) {
    if (!p[i]) continue;
    rep(j, i * i, MAX_P, i) p[j] = 0;
  }
  vi pH, pW;
  rep(i, MAX_P - (G[0] - S[0])) {
    if (p[i] && p[i + (G[0] - S[0])]) pH.eb(i);
  }
  rep(i, MAX_P - (G[1] - S[1])) {
    if (p[i] && p[i + (G[1] - S[1])]) pW.eb(i);
  }
  // 操作dを数える
  vector dist(H, vector(W, ai2{(int)1e9, (int)1e9}));
  dist[S[0]][S[1]][0] = 0;
  using ai4 = array<int, 4>;
  priority_queue<ai4, vector<ai4>, greater<ai4>> pq;
  int ans = 1e9;
  auto move_ok = [&](int x, int y) {
    if (x < 0 || x >= H || y < 0 || y >= W) return false;
    return C[x][y] != '#';
  };
  pq.push(ai4{0, S[0], S[1], 0});
  rep(b, H * W) {
    while (pq.size()) {
      auto [d, x, y, f] = pq.top();
      pq.pop();
      if (dist[x][y][f] != d) continue;
      {
        // a
        int x2 = x + 1, y2 = y;
        if (move_ok(x2, y2) && dist[x2][y2][f] > d) {
          dist[x2][y2][f] = d;
          pq.push(ai4{d, x2, y2, f});
        }
      }
      {
        // c
        int x2 = x, y2 = y + 1;
        if (move_ok(x2, y2) && dist[x2][y2][f] > d) {
          dist[x2][y2][f] = d;
          pq.push(ai4{d, x2, y2, f});
        }
      }
      {
        // d
        int x2 = x, y2 = y - 1;
        if (move_ok(x2, y2) && dist[x2][y2][1] > d + 1) {
          dist[x2][y2][1] = d + 1;
          pq.push(ai4{d + 1, x2, y2, 1});
        }
      }
    }
    if (b > 0) {
      int h = lb(pH, b), w = lb(pW, dist[G[0]][G[1]][1]);
      if (h < sz(pH) && w < sz(pW))
        chmin(ans, pH[h] * 2 + (G[0] - S[0]) + pW[w] * 2 + (G[1] - S[1]));
    }
    // b
    // cerr<<"B: "<<b<<endl;
    rep(i, 1, H) {
      rep(j, W) {
        if (C[i][j] == '#') continue;
        rep(k, 2) {
          int d = dist[i][j][k];
          int x2 = i - 1, y2 = j;
          if (move_ok(x2, y2)) {
            dist[x2][y2][k] = d;
            pq.push(ai4{d, x2, y2, k});
            // cerr<<"("<<x2<<','<<y2<<','<<k<<") = "<<d<<endl;
          }
        }
      }
    }
    rep(i, W) { rep(k, 2) dist[H - 1][i][k] = 1e9; }
  }
  cout << (ans == 1e9 ? -1 : ans) << '\n';
}
0