SRM440 Div2 500
問題
迷路が与えられる。迷路をねずみがゴールまで進む時、分岐点はいくつあったかを求める。
考え方
制約に「there will exist exactly one path between them.」とあるのでdfsで計算できる。
再帰するときに分岐点数を保持しておいて、分岐点を通ったら+1する。ゴールに着いたら終了。
反省
制約をちゃんと呼んでなくて、複数パスが存在した場合のこととか最短路を通るべきなのかとか考えたりして時間浪費した。
結局、bfsでゴールまでのパスを見つけて、そのパス上の点で分岐点があったかを計算した。
問題文、制約をちゃんと読みましょう。推測しない。