Atcoder水色精進記録
ABC246
E - Bishop 2
https://atcoder.jp/contests/abc246/tasks/abc246_e
アルゴリズム・データ構造
01-BFS
考察
最短手のためBFS？
→マス数はNN=15001500=2,250,000=2.2510**6
1手で対角線は無限に行くことが出来るので
進行方向はcost0、進行方向と90度曲がる方向はcost1として捉えると01-BFSでいけそう
最大でも全マス進行方向2種類の2NNでいけそう
提出
感想
訪れた場所への値の更新は要注意
基本的には下記二点
・既に入れようとしているコスト以下の値が入っている場合はqueに追加しないために、queに入れた際に値を更新する
・popした後に、記録していた値より大きい（queに追加する際に記録を更新しているため＝の場合は実施）場合は何もせずにcontinue
上記方針で実施すれば、queに対して、記録/que内の未実施の値以上の値が入ることはない。