ABC 246 E - Bishop 2

atcoder.jp

解説では拡張ダイクストラや01BFSだけど、ずっとTLEで通すまで時間がかかったので忘れないようメモ。

右上がりのラインと左上がりのラインで到達できる範囲を頂点と考える。 すると各マスの右上がりラインと左上がりラインに辺を貼ることで、曲がるときにコスト1と考えることができ、普通のBFSの最短経路で求めることができる。 ただ始点/終点はそれぞれ2つあるので、簡便のため、始点/終点の頂点を作成し、それぞれのマスのラインの頂点に辺をはる、この時結果としては+1になるのに注意。

最初に辺をまとめるところはN * N * 2の頂点を用意して一旦UnionFindでまとめてからグラフを構築するか、 グラフに頂点を足せるようにしておいて、左上、右上のマスと連結できないときにあたらしく頂点を増やせばよい。

class Graph
  def initialize; @g = []; end
  def add_node; @g << []; @g.size - 1; end
  def add_edge(a,b); ... ; end
  def bfs(s,t); ... ; end
end

提出 : atcoder.jp