結果

問題 No.3121 Prime Dance
ユーザー Nzt3
提出日時 2025-04-06 04:44:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 74 ms / 2,000 ms
コード長 3,771 bytes
コンパイル時間 3,442 ms
コンパイル使用メモリ 296,676 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-08 23:39:25
合計ジャッジ時間 4,961 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:162:35: warning: narrowing conversion of ‘f’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
  162 |             distC[d].eb(ai3{x2,y2,f});
      |                                   ^

ソースコード

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=1'000'00;

int main(){
  vi prime(MAX_P,1);
  prime[0]=prime[1]=0;
  rep(i,2,MAX_P){
    if(!prime[i])continue;
    rep(j,i*i,MAX_P,i)prime[j]=0;
  }
  int H,W;
  cin>>H>>W;
  using ai2=array<int,2>;
  ai2 S,G;
  cin>>S[0]>>S[1];
  cin>>G[0]>>G[1];
  --S[0],--S[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));
  }

  // A<=B,C<=Dとなる
  vi pH,pW;
  rep(i,MAX_P){
    if(i+(S[0]-G[0])<MAX_P&&prime[i]&&prime[i+(S[0]-G[0])]){
      pH.eb(i);
    }
    if(i+(S[1]-G[1])<MAX_P&&prime[i]&&prime[i+(S[1]-G[1])]){
      pW.eb(i);
    }
  }

  using ai3= array<int,3>;
  
  auto move_ok=[&](int x,int y){
    if(x<0||x>=H||y<0||y>=W)return false;
    return C[x][y]!='#';
  };
  
  vector<vector<ai3>> distC(H*W); 
  distC[0].eb(ai3{S[0],S[1],0});
  int ans=1e9;
  rep(a,H*W){
    vector<vector<ai2>> dist(H,vector(W,ai2{(int)1e9,(int)1e9}));
    deque<ai3>bfs;
    int base=0;
    while(base<H*W||!bfs.empty()){
      int d=1e9;
      if(!bfs.empty()){
        auto [x,y,l]=bfs.front();
        d=dist[x][y][l];
      }
      if(d>=base){
        fore(i,distC[base]){
          if(dist[i[0]][i[1]][i[2]]>base){
            dist[i[0]][i[1]][i[2]]=base;
            bfs.push_front(i);
          }
        }
        base++;
        continue;
      }
      auto [x,y,l]=bfs.front();
      bfs.pop_front();
      d=dist[x][y][l];
      // B
      {
        int x2=x-1,y2=y;
        if(move_ok(x2,y2)&&dist[x2][y2][l]>d){
          dist[x2][y2][l]=d;
          bfs.push_front(ai3{x2,y2,l});
        }
      }
      // C
      {
        int x2=x,y2=y+1;
        if(move_ok(x2,y2)&&dist[x2][y2][1]>d+1){
          dist[x2][y2][1]=d+1;
          bfs.push_back(ai3{x2,y2,1});
        }
      }
      // D
      {
        int x2=x,y2=y-1;
        if(move_ok(x2,y2)&&dist[x2][y2][1]>d){
          dist[x2][y2][1]=d;
          bfs.push_front(ai3{x2,y2,1});
        }
      }
    }
    if(a>0){
      int c=dist[G[0]][G[1]][1];
      int h=lb(pH,a),w=lb(pW,c);
      if(h<sz(pH)&&w<sz(pW)){
        chmin(ans,pH[h]*2+(S[0]-G[0])+pW[w]*2+(S[1]-G[1]));
      }
    }

    // rep(i,H){
    //   rep(j,W)cerr<<dist[i][j][0]<<' ';
    //   cerr<<endl;
    // }
    // cerr<<endl;
    // rep(i,H){
    //   rep(j,W)cerr<<dist[i][j][1]<<' ';
    //   cerr<<endl;
    // }
    // cerr<<endl;
    

    rep(i,H*W)distC[i].clear();
    rep(x,H){
      rep(y,W){
        rep(f,2){
          int x2=x+1,y2=y,d=dist[x][y][f];
          if(move_ok(x2,y2)&&d<H*W){
            distC[d].eb(ai3{x2,y2,f});
          }
        }
      }
    }
  }
  cout<<(ans==1e9?-1:ans)<<'\n';
}
0