ABC176 D. Wizard in Maze
Difficulty:1248
問題
グリッドがある。グリッド上を2通りの方法で移動することができる。
上下左右隣接するマスに移動する
自分周辺の5×5のマスのいずれかに移動する
ある地点sx,syからtx,tyに移動するとき、2番目の移動の使用回数は最小で何回か。
解法
01BFSをすればよい。1番目の移動の際はpush_frontし、2番目の移動の際にはpush_backする。同じマスを訪れた時の処理に注意。
実装
code:cpp
bool solve(){
LL(h,w);
LL(sx,sy);
LL(tx,ty);
sx--,sy--,tx--,ty--;
vector<str>s(h);cin >> s;
vector dist(h,vector(w,INF));
//01BFS
deque<pair<ll,ll>>dq;
dq.push_back({sx,sy});
vector used(h,vector(w,0));
while(dq.size()){
autox,y = dq0;dq.pop_front(); //4方向
rep(i,4){
ull nx = x+dxi,ny = y+dyi; if(nx<h&&ny<w){
dq.push_front({nx,ny});
}
}
}
}
//ワープ
rep(i,-2,3)rep(j,-2,3){
ull nx = x+i,ny = y+j;
if(nx<h&&ny<w){
dq.push_back({nx,ny});
}
}
}
}
}
return false;
}