差分
このページの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 | ||
|---|---|---|---|
| 行 289: | 行 289: | ||
| ■■■ | ■■■ | ||
| - | さて、迂回するとき、上側を迂回するとして $s→p→q→t$ と通ればよい。 | + | ■は同じ大きさのものが同じ高さに並ぶことはあり得るが、数マスだけ上下にズレたりとかはない。 |
| + | 迂回するとき、上側を迂回するとして $s→p→q→t$ と通ればよい。 | ||
| ここで、$p, | ここで、$p, | ||
| 行 296: | 行 297: | ||
| $s→p$ は最短で行けるか？ | $s→p$ は最短で行けるか？ | ||
| - | これが行けないとすると、以下のような感じで $s-p$ 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ないので、最短で行ける。$q→t$ も同様。 | + | まず、$p$ の属する縦列もこの範囲では白マスである（1つの■の塊の周囲は必ず白マス）。よって、$s$ から上と右に移動を繰り返して、$p$ と同じ行または列に来れたら、後は最短距離で行ける。 |
| + | |||
| + | その道中まではどうかというと、「上にも右にも進めない」状態にならない限り、どちらかには進める。そしてどちらかに進み続ければいつかは $p$ と同じ行または列に行ける。 | ||
| + | |||
| + | 上にも右にも進めない状態、しかもそれが $s$ からの移動で回避できない状態とは、以下のような感じで $s-p$ 間をナナメに遮る黒マスがあるということになるが、作り方からしてそれはあり得ない。よって $s→p$ は最短で行ける。$q→t$ も同様。 | ||
| p | p | ||
| 行 305: | 行 310: | ||
| よって、最も大きい■を縦か横のいずれか一方に迂回する必要性だけ考えれば残りは最短で行ける。 | よって、最も大きい■を縦か横のいずれか一方に迂回する必要性だけ考えれば残りは最短で行ける。 | ||
| - | === 迂回距離を求める === | + | === 迂回すべき■のサイズ・迂回距離を求める === |
| 迂回する方向を縦に決め打ちし、横は最短距離とする（縦横反転して2通り試して大きい方を答えとする）。 | 迂回する方向を縦に決め打ちし、横は最短距離とする（縦横反転して2通り試して大きい方を答えとする）。 | ||
