CodeIQ過去問集32：一番楽な待ち合わせ

本稿はCodeIQで2015年6月22日～7月6日に出題された コード銀行：一番楽な待ち合わせ という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

一番楽な待ち合わせ

次の図のような、格子状の土地の各番号部分に人が住んでいます。

このうちの数名が、どこかで待ち合わせをすることになりました。 待ち合わせる場所は、番号のついた場所に限り、移動は横・縦の実線部分しか通ることができません。 また、隣り合った各地点同士の距離を1とします。

このとき、個々の移動距離の合計が最も小さくなるような待ち合わせ場所を探してください。

たとえば、次のように1, 10, 12の人たちが集合するには7の場所が最適で、この場合は移動距離の合計が6になります。

【問題】

格子状の土地について、横・縦のサイズと、待ち合わせに参加する人の番号が標準入力から与えられます。 最適な待ち合わせ場所を見つけ、そこに移動する距離の合計を標準出力に出力してください。

【入力】

標準入力から、以下の形式で複数の整数値を読み込みます。

W H
N
a1 a2 … aN

1行目のW, Hは土地のサイズ(1≦W, H≦1000)を表し、半角スペースで区切られています。 ただし、各値は距離ではなく家（点）の個数です。つまり、問題文の例ではW = 5, H = 3になります。 2行目のNは、待ち合わせに参加する人の数(1≦N≦W×H)です。 3行目にはN個の整数値が半角スペース区切りで書かれています。この値は待ち合わせに参加する人の家番号（1～W×H）です。

【出力】

標準出力に、整数値を1つ出力してください。行末での改行は有無を問いません

【入出力サンプル】

Case 1: Input

5 3
3
1 10 12

Case 1: Output

6

Case 2: Input

10 6
5
31 18 39 55 47

Case 2: Output

16

【解答方法】

machiawase.zipをダウンロードしてください。中には以下のファイルが含まれています。

• sample1.in.txt, sample1.out.txt, sample2.in.txt, sample2.out.txt: 例で示したデータと、その解答です。
• small.in.txt, large.in.txt: これを入力として、正しい実行結果が得られるプログラムを書いてください

（解答・解説は後日）