Day 2 Task 3: 迷路 (Maze)
オンタリオ州の南部では，
多くのトウモロコシ農家が図のようなトウモロコシの茎で迷路を作る．
穀物が収穫された後，迷路は秋に作られる．
2010年に，今までで最高の迷路を設計するのを助ける時間が，
あなたにはまだある．
障害物（木や建物など）があってトウモロコシを育てることができない場所を除いて，
畑には，トウモロコシの茎が植えられている．
茎はとても高く，迷路の壁を形づくっている．
通路は，いくつかの 1 メートル四方の区画内の茎を踏みつぶすことにより，
正方形の格子状の領域の上に作られる．
境界の区画の 1 つが入口である．
また，区画の 1 つが迷路の中心(core)である．
ジャックはトウモロコシ畑の迷路を毎年訪れており，
入口から中心までの経路をすぐに見つけることができる．
あなたは新しい迷路を設計している．
あなたの仕事は，
ジャックが通らなければならない区画の個数ができるだけ多くなるように，
どの茎を踏みつぶすかを決めることである．
どの区画が入口であるかは，採点プログラムが決定する（入口は境界にただ 1 つ存在する）．
また，どの区画が中心（ジャックがそこに到達するのに最も長く移動する必要がある場所）であるかも，
採点プログラムが決定する．
長方形の畑の地図はテキストで表される．
例えば， 8 本の木が生えている 6 メートル× 10 メートルの畑は
##X#######
###X######
####X##X##
##########
##XXXX####
##########
のように表される．
記号 # はトウモロコシの茎が生えている区画を表し，
X は障害物（木など）があって踏みつぶして通路を作ることができない区画を表す．
トウモロコシにより占有されている区画をいくつか踏みつぶすことで，
畑を迷路に変える．
踏みつぶされた区画のうちの 1 つ（入口）は畑の境界になければならない．
それ以外の踏みつぶされた区画は，内部になければならない．
目標は入口から中心までの最短経路をできるだけ長くすることである．
最短経路の長さはジャックが通らなければならない区画の個数（入口と中心を含む）である．
ある区画から他の区画に移動することができるのは，
両方の区画が踏みつぶされていて，それらが一辺を共有しているときに限る．
あなたの提出ファイルでは，
踏みつぶされた区画はピリオド (.) で表されていなければならない．
ちょうど 1 つの踏みつぶされた区画が境界になければならない．
以下に例を挙げる．
#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########
以下では，説明のために，
入口を E で，中心を C で表す．
また，経路上のこれら以外の区画を + で表す．
経路の長さは 12 である．
#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########
フォルダー /home/ioi2010-contestant/maze には，
field1.txt field2.txt などの名前のいくつかのテキストファイルが置いてあり，トウモロコシ畑の地図を含む．
これらを maze1.txt maze2.txt
などの名前のファイルにコピーせよ．
そして，いくつかの記号 # をピリオドに置き換えることで，
これらを有効な迷路に変換せよ．
注意: 採点サーバーは，有効な解答に対して（経路の長さに関わらず），各小課題に 1 点を与える (Grading Server Public Test)．
また，採点サーバーは，リリーストークンを使った提出に対して，残りの得点を与える(Grading Server Release Test)．
この課題の総得点は，0 以上 110 以下の最も近い整数に丸められる．
小課題 1 [最高 11 点]
ファイル field1.txt は上に例として挙げた畑（大きさ 6 × 10）を表す．
この畑に対する迷路を maze1.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/20 のうち小さい方である．
なお，サンプル解法により，3.98 点の得点が得られる．
小課題 2 [最高 11 点]
ファイル field2.txt は大きさが 100 × 100 の畑を表す．
この畑に対する迷路を maze2.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/4000 のうち小さい方である．
小課題 3 [最高 11 点]
ファイル field3.txt は大きさが 100 × 100 の畑を表す．
この畑に対する迷路を maze3.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/4000 のうち小さい方である．
小課題 4 [最高 11 点]
ファイル field4.txt は大きさが 100 × 100 の畑を表す．
この畑に対する迷路を maze4.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/4000 のうち小さい方である．
小課題 5 [最高 11 点]
ファイル field5.txt は大きさが 100 × 100 の畑を表す．
この畑に対する迷路を maze5.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/5000 のうち小さい方である．
小課題 6 [最高 11 点]
ファイル field6.txt は大きさが 11 × 11 の畑を表す．
この畑に対する迷路を maze6.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/54 のうち小さい方である．
小課題 7 [最高 11 点]
ファイル field7.txt は大きさが 20 × 20 の畑を表す．
この畑に対する迷路を maze7.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/33 のうち小さい方である．
小課題 8 [最高 11 点]
ファイル field8.txt は大きさが 20 × 20 の畑を表す．
この畑に対する迷路を maze8.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/95 のうち小さい方である．
小課題 9 [最高 11 点]
ファイル field9.txt は大きさが 11 × 21 の畑を表す．
この畑に対する迷路を maze9.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/104 のうち小さい方である．
小課題 10 [最高 11 点]
ファイル fieldA.txt は大きさが 200 × 200 の畑を表す．
この畑に対する迷路を mazeA.txt に作成せよ．
入口から中心までの最短距離が P であるとき，
この小課題に対するあなたの得点は
11 と 10P/7800 のうち小さい方である．
実装の詳細
- これは 出力のみの課題 (output-only task) である．
- 実装フォルダー (Implementation folder): /home/ioi2010-contestant/maze/ (プロトタイプ: maze.zip)
- 選手が提出するファイル (To be submitted by contestant): maze1.txt maze2.txt maze3.txt maze4.txt maze5.txt maze6.txt maze7.txt maze8.txt maze9.txt mazeA.txt
- 提出ファイルのインターフェース (Contestant interface): なし
- 採点プログラムのインターフェース (Grader interface): なし
- 採点プログラムのサンプル (Sample grader): grader.c または grader.cpp または grader.pas
- 採点プログラムの入力のサンプル (Sample grader input): grader.in.1 grader.in.2 など．
注意: 実装フォルダーはとても単純な解答 maze1.txt, maze2.txt ... などを含む．テストするには，これらを grader.in.1 grader.in.2 などにコピーせよ．
- 採点プログラムの入力のサンプルに対して期待される出力:
もし入力が小課題 N についての有効な迷路であれば，
採点プログラムは OK N P を出力する．
ここで， P は経路の長さである．
- コンパイルと実行 (コマンドライン): runc grader.c または runc grader.cpp または runc grader.pas
- コンパイルと実行 (gedit プラグイン): 採点プログラムを編集中に Ctrl-R.
- 提出 (コマンドライン): submit maze1.txt または submit maze2.txt など．submit コマンドでどのファイルが指定されているかに関わらず，
実装フォルダー内の全ての .txt ファイルが提出される．
- 提出 (gedit プラグイン): .txt ファイルを編集中に Ctrl-J．