No.037 D 問題 コード 各マスから進める方向のマスに有向辺を張ったグラフを考える. グラフは DAG となる. グラフのあるノードを終点とする経路の数は, そのノードへ入る辺のもう片方の端点を終着とする経路の数を合計し, そのノードを起点かつ終点にする経路分の1を足したものとなる. あとはグラフをトポロジカルソートし, 最初から順番にそのノードを終点とする数を計算し, すべてを合計する.