結果

問題 No.3679 なんかでっかい虫リターンズ
コンテスト
ユーザー kukone
提出日時 2026-09-05 13:27:57
言語 C++23
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 7 ms / 2,000 ms
+ 530µs
コード長 1,886 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,234 ms
コンパイル使用メモリ 387,108 KB
実行使用メモリ 9,764 KB
最終ジャッジ日時 2026-09-05 13:28:23
合計ジャッジ時間 5,705 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge4_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll=long long;
using ld=long double;
using st=string;
using P=pair<ll,ll>;
typedef atcoder::modint mint;
ll inf=9e18;
template<class... T>
constexpr auto max(T... a){return max(initializer_list<common_type_t<T...>>{a...});}
template<class... T>
constexpr auto min(T... a){return min(initializer_list<common_type_t<T...>>{a...});}
template<typename T, int s, int i = 0>
auto vec(const ll (&sizes)[s], const T& init = T()){
  if constexpr(i < s) return vector(sizes[i], vec<T, s, i+1>(sizes, init));
  else return init;
}


ll h,w,a,b,r1,r2,c1,c2,p,q;
struct xys{ll x,y,s;};
ll bfs_grid(vector<st> &map,vector<vector<vector<ll>>> &step,xys s,ll state,ll d=4){
  vector<ll> dx,dy;
  step=vec<ll>({h,w,state},-1);
  if(d==4){dx={1,0,-1,0};dy={0,1,0,-1};}
  if(d==8){dx={1,1,0,-1,-1,-1,0,1};dy={0,1,1,1,0,-1,-1,-1};}
  if(s.s==0&&r1<=s.x&&s.x<=r2&&c1<=s.y&&s.y<=c2) s.s=1;
  if(s.s==1&&s.x==p&&s.y==q) s.s=2;
  if(s.s==2&&s.x==a&&s.y==b) return 0; // Goal
  step[s.x][s.y][s.s]=0;
  queue<xys> Q;
  Q.push(s);
  while(!Q.empty()){
    auto pre=Q.front();
    Q.pop();
    for(ll i=0;i<d;i++){
      ll x=pre.x+dx[i],y=pre.y+dy[i],s=pre.s;
      // cout<<pre.x<<pre.y<<pre.s<<"\n";
      if( x<0 || y<0 || h<=x || w<=y ) continue;
      // if(0) s=s+1;
      if(step[x][y][s]!=-1) continue;

      if(s==0&&r1<=x&&x<=r2&&c1<=y&&y<=c2) s=1;
      if(s==1&&x==p&&y==q) s=2;
      if(s==2&&x==a&&y==b) return step[pre.x][pre.y][s]+1; // Goal

      step[x][y][s]=step[pre.x][pre.y][pre.s]+1;
      Q.push({x,y,s});
      // cout<<"->"<<x<<y<<s<<"\n";
    }
  }
  return -1;
}

int main(){
  cin>>h>>w>>a>>b>>r1>>c1>>r2>>c2>>p>>q;
  --a,--b,--r1,--c1,--r2,--c2,--p,--q;
  auto v=vec<st>({h},"");
  auto step=vec<ll>({h,w,3},0);
  cout<<bfs_grid(v,step,{a,b,0},3)<<"\n";
}
0