perogram

C - Infinite Grid

Quiz

https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c

Submit

https://atcoder.jp/contests/s8pc-6/submissions/4981908

解法

  • editorialの通り

感想

  • 100個くらいつなげて到達可能なら行けそう
  • 迷路で到達可能かどうか、ということで幅優先で解いたらTLEだった
  • editorialのようにdpで解いたらAC

学び

  • 迷路は可能ならdpで解くべし

(自分的)落とし穴

bool dp[R][C]; // 到着可能か
FOR(i, 0, R){
    FOR(j, 0, C){
        dp[i][j] = false;
    }
}
  • フラグは初期化しよう
  • 1次元フラグだといつもvectorを使うので初期化は省略できるが、今回は2次元だったので配列で書いたら初期化を忘れていた

最短経路の本 レナのふしぎな数学の旅

最短経路の本 レナのふしぎな数学の旅

  • 作者: P.グリッツマン,R.ブランデンベルク,石田基広
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/04/05
  • メディア: 単行本(ソフトカバー)
  • クリック: 1回
  • この商品を含むブログを見る