読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

TopCoder SRM 707 Div1 Easy MazeConstruct

SRM

不参加だったけどEasyもMediumもミスしてたのでまぁ助かったか。
https://community.topcoder.com/stat?c=problem_statement&pm=14518

問題

整数Kが与えられる。
N*Mのグリッドで構築され(N,Mは50以下)、一部のセルが埋まった迷路のうち、左上から右下マスまで隣接マスをたどって移動する際の最小移動マス数がKになるものを構築せよ。

解法

空きマス目が(K+1)となる道を作ることを考えよう。
右にずっと移動して下に移動する迷路を作れば移動マス数が(N+M-2)となるので、K≦98の場合はこれでよい。

それ以上は何かしら折り返しが必要である。
まず上端に以下のような構成を作ると、51マス空きマスを配置できる。

..................................................
#################################################.

あとはその下に以下の構成をつなげていけば、102マスずつ空きマスを配置できる。

..................................................
.#################################################
..................................................
#################################################.

残りはこんな感じで少し短めの折り返しを作ろう。
折り返しの長さでマス数を2ずつ調整できるので、あとは最終行の有無で1マス調整できる。

############......................................
############.#####################################
############......................................
#################################################.

まとめ

なんだこの問題。

広告を非表示にする