ABC170 F Pond Skater
Diff 1968.
東西南北1マスのみであれば通常のBFSで解ける. 今回は1~Kマスなのでこれをどう高速化するか, である.
とにかく同じマスを定数回しか見なければ間に合う. 考察すると, 蓮の葉があったり枠外だったり
$ dist_{nx,ny} \leq dist_{i,j}
だったりした途中で打ち切ることによって間に合う, ということが分かる(頭の中で考えると正当性は示せる).
未訪問マスのみ値を更新していくことに注意.
実装例:
https://atcoder.jp/contests/abc170/submissions/18950149