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だった
  • https://atcoder.jp/contests/s8pc-6/submissions/4981854
  • 190点/400点 まではもらえた
• editorialのようにdpで解いたらAC

学び

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

(自分的)落とし穴

bool dp[R][C]; // 到着可能か
FOR(i, 0, R){
    FOR(j, 0, C){
        dp[i][j] = false;
    }
}

• フラグは初期化しよう
• 1次元フラグだといつもvectorを使うので初期化は省略できるが、今回は2次元だったので配列で書いたら初期化を忘れていた

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