差分
このページの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 | ||
|---|---|---|---|
| 行 302: | 行 302: | ||
| 上にも右にも進めない状態とは、以下のような感じで s−p 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。 | 上にも右にも進めない状態とは、以下のような感じで s−p 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。 | ||
| - | （任意の k に対し、Lv.k 盤面は最外周1マスを白マスで覆われている。従って、Lv.k+1 盤面を作る際に、隣接する2つの Lv.k 盤面の合体により新たな■の隣接が発生することはない。あるとしたら Lv.k 盤面の中に既に含まれている場合だが、これを再帰的に適用した場合、Lv.1盤面に含まれていないといけないことになるが、Lv.1盤面に■の斜めの隣接はない。） | + | （任意の k に対し、Lv.k 盤面は最外周1マスを白マスで覆われている。従って、Lv.k+1 盤面を作る際に、2つの Lv.k 盤面の合体により新たな■の隣接が発生することはない。あるとしたら Lv.k 盤面の中に既に含まれている場合だが、これを再帰的に適用した場合、Lv.1盤面に含まれていないといけないことになるが、Lv.1盤面に■の斜めの隣接はない。） |
| よって s→p は最短で行ける。q→t も同様。 | よって s→p は最短で行ける。q→t も同様。 | ||
