差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:contest_history:atcoder:2020:0314_panasonic2020 [2020/03/16] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2020:0314_panasonic2020 [2020/03/16] (現在) – [解法] ikatakos | ||
---|---|---|---|
行 301: | 行 301: | ||
その道中まではどうかというと、「上にも右にも進めない」状態にならない限り、どちらかには進める。そしてどちらかに進み続ければいつかは $p$ と同じ行または列に行ける。 | その道中まではどうかというと、「上にも右にも進めない」状態にならない限り、どちらかには進める。そしてどちらかに進み続ければいつかは $p$ と同じ行または列に行ける。 | ||
- | 上にも右にも進めない状態、しかもそれが $s$ からの移動で回避できない状態とは、以下のような感じで $s-p$ 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。よって $s→p$ は最短で行ける。$q→t$ も同様。 | + | 上にも右にも進めない状態とは、以下のような感じで $s-p$ 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。 |
+ | (任意の $k$ に対し、Lv.$k$ 盤面は最外周1マスを白マスで覆われている。従って、Lv.$k+1$ 盤面を作る際に、2つの Lv.$k$ 盤面の合体により新たな■の隣接が発生することはない。あるとしたら Lv.$k$ 盤面の中に既に含まれている場合だが、これを再帰的に適用した場合、Lv.1盤面に含まれていないといけないことになるが、Lv.1盤面に■の斜めの隣接はない。) | ||
+ | |||
+ | よって $s→p$ は最短で行ける。$q→t$ も同様。 | ||
p | p |