第三回 アルゴリズム実技検定 G問題

PAST003G

問題文に金移動とあり将棋の金のような動きだが，移動方法はあまり重要ではなく，基本はBFS. ただし，そのままやると無限に広がるグリッドなので無限ループに入ってしまう．

そこで，グリッドの範囲を狭くすることを考える． 遠くに行き過ぎるメリットは無さそう． 実際，スタートとゴールを両方含む長方形 \(R\) の外にでる意味は ほとんど無さそう． ただし，少し迂回してからゴールするルートがあるため， \(R\) は一回り大きくとっておく必要がある．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

template<typename T> bool in(T x, set<T> &s){ return s.find(x) != s.end(); }

int main() {

  ll n, m, k, q;

  cin >> n;

  ll x, y; cin >> x >> y;

  set<pll> v;

  rep(i,n){

    ll a,b; cin>>a >> b;

    v.insert({a,b});

  }

 

  // map

  vll dx = vll({1,0,-1,1,-1,0});

  vll dy = vll({1,1,1,0,0,-1});

  queue<pll> que;

  map<pll,bool> vis;

  map<pll,ll> dis;

  auto push = [&](ll x, ll y, ll d) {

    if(vis[{x,y}]) return;

    vis[{x,y}] = true;

    dis[{x,y}] = d;

    que.push({x,y});

  };

  push(0ll, 0ll, 0ll);

  while(que.size()){

    ll cx,cy; tie(cx,cy) = que.front();

    que.pop();

    ll cd = dis[{cx,cy}];

   

    rep(di,6){

      ll nx = cx + dx[di];

      ll ny = cy + dy[di];

      pll pa = make_pair(nx,ny);

      ll K = 210;

      if(!in(nx, -K, K)) continue;

      if(!in(ny, -K, K)) continue;

      if(in(pa, v)) continue;

      push(nx,ny, cd+1);

    }

  }

  if(!vis[{x,y}]) cout << -1 << endl;

  else cout << dis[{x,y}] << endl;

 

  return 0;

}