プログラミング問題「渋滞緩和」

※この問題は、 「RCO presents 日本橋ハーフマラソン 本戦」で出題した問題 を改題したものです。

問題文

\(H\) 行 \(W\) 列のマスからなるマップがあります。そのうち \(K\) 個のマスには、1台の車があります。

一番上の行を \(1\) 行目、一番左の列を \(1\) 列目とし、\(r\) 行 \(c\) 列にあるマスを \((r, c)\) と表します。

\(K\) 台の車それぞれに、最初にいるマス（初期マスと呼ぶ）と目的地となるマス（目的マスと呼ぶ）が与えられます。 車 \(i\) の初期マスは \((A_i, B_i)\) です。また、車 \(i\) の目的マスは \((C_i, D_i)\) です。 あなたはそれぞれの車に対して、各時刻 \(t\) (\(0 \leq t \lt L\), \(t\)は整数) で辺で隣接したマスへの移動を指示できます。すると、時刻 \(t+1\) で、その車は指示されたマスに移ります。 ただし、以下のような移動を指示することはできません。

  • 移動先のマスに時刻 \(t\) の時点で車が存在する場合
  • 同時に複数の車の移動先が同じマスになる場合
  • 移動先がマップの外側になる場合

1回の指示で、\(K\) 台全ての車それぞれに対して、隣接した4方向への移動を指示、あるいは、移動せず、今いるマスに留まることを指示します。

最大で \(T\) 回の指示を出すことができます。それぞれの車を、できるだけ目的マスに近づけてください。

車 \(i\) の最終的な位置を \((r_i, c_i)\) として、\(penalty = \sum_{i=1}^{N}(|r_i - C_i| + |c_i - D_i|)\) で表される残距離が小さいほど良い解です。

\(penalty = 0\) にできる場合は、できるだけ少ない指示回数で \(penalty = 0\) にすることを目指してください。

入力

入力は以下の形式です。すべての値は整数です。入力データのファイル名 input_XXX.txt の XXX が、 \(K\) の値に対応します。

H W K T
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_K B_K C_K D_K
  • \(H\) はマップの行数を表す整数で、\(H=20\) を満たします。
  • \(W\) はマップの列数を表す整数で、\(W=20\) を満たします。
  • \(K\) はマップ上の車の数を表す整数で、\(K=20, 40, 60, 80, 100, 120, 140, 160, 180, 200\) のいずれかです。
  • \(T\) は車に出せる指示の回数の最大値を表す整数で、\(T=10000\) を満たします。
  • \(A_i\) および \(B_i\) は車 \(i\) の初期マス \((A_i, B_i)\) を表す整数で、 \(1 \leq A_i \leq H\), \(1 \leq B_i \leq W\) を満たします。
  • \(C_i\) および \(D_i\) は車 \(i\) の目的マス \((C_i, D_i)\) を表す整数で、 \(1 \leq C_i \leq H\), \(1 \leq D_i \leq W\) を満たします。
  • \(i \neq j\) ならば、\((A_i, B_i) \neq (A_j, B_j)\) かつ \((C_i, D_i) \neq (C_j, D_j)\) を満たします。

出力

回答は以下の形式で出力してください。

L
movement_0
movement_1
:
movement_{L-1}
  • \(1\) 行目に指示回数 \(L (0 \leq L \leq T)\) を出力してください。
  • \(t+2 (0 \leq t \lt L)\) 行目には、時刻 \(t\) の時に各車へ出す指示を表す文字列 \(movement_t\) を出力してください。
  • \(movement_t (0 \leq t \lt L)\) は \(K\) 文字からなる文字列で、\(movement_t\) の \(i\) 文字目は、車 \(i\) へ出す時刻 \(t\) での指示を表します。
  • 各指示は、以下の文字によって表されます。
    U
    現在のマスより1行小さいマスに移動します。（上に移動します）
    D
    現在のマスより1行大きいマスに移動します。（下に移動します）
    L
    現在のマスより1列小さいマスに移動します。（左に移動します）
    R
    現在のマスより1列大きいマスに移動します。（右に移動します）
    -
    移動しません。

テストケースの生成について

各テストケースは次の手順で生成しました。

  • 初期マスの候補となる\(K\)個のマスを、\(H \times W\) 個のマスの中から、重複しないようにランダムに選ぶ。
  • それらの初期マスの候補を、ランダムに \(K\) 台の車に割り当てる。
  • 目的マスの候補となる\(K\)個のマスを、\(H \times W\) 個のマスの中から、重複しないようにランダムに選ぶ。
  • それらの目的マスの候補を、ランダムに \(K\) 台の車に割り当てる。

入力例1

6 6 2 100
3 3 4 5
6 2 2 4

注意: この入力はテストケースとしての制約を満たしていません。説明のために用意した例です。

車1の初期マスを \(1\)、車1の目的マスを \(X\)、車2の初期マスを \(2\)、車2の目的マスを \(Y\) としたマップを以下に図示します。

出力例1

4
RR
RU
DU
-L

全ての指示を実行した後のマップは以下のようになります。車1は目的マスに到着しています。

  • 時刻 \(0\) では車1も車2も右に移動します。
  • 時刻 \(1\) では車1は右に、車2は上に移動します。
  • 時刻 \(2\) では車1は下に、車2は上に移動します。
  • 時刻 \(3\) では車1は移動しません。車2は左に移動します。
  • この出力によって得られる結果は、以下のように計算されます。
    • 車1の目的マスは \((4,5)\) で、最終的な位置は \((4,5)\) です。
    • 車2の目的マスは \((2,4)\) で、最終的な位置は \((4,2)\) です。
    • よって \(penalty=(|4-4|+|5-5|)+(|2-4|+|4-2|)=4\) です。

入力例2

20 20 100 10000
6 3 17 14
20 13 18 2
18 11 2 13
8 2 2 20
4 4 7 18
18 8 10 15
11 9 17 3
19 13 5 15
16 1 16 11
15 6 11 10
4 2 8 20
1 6 12 3
15 10 1 6
9 8 10 7
14 7 17 10
8 10 9 2
5 17 10 5
18 6 13 2
8 17 1 12
7 20 15 19
3 7 8 12
19 7 6 14
5 19 3 7
4 20 6 17
14 16 20 19
14 3 7 4
8 18 20 12
2 15 4 2
6 7 17 4
8 12 4 9
12 1 14 13
1 19 2 9
5 16 19 19
9 19 5 1
9 17 12 15
15 17 2 3
1 13 13 4
18 4 6 11
19 3 4 6
14 11 10 12
3 12 3 9
11 20 1 20
1 9 9 10
17 14 11 16
13 17 13 11
1 20 2 6
19 5 6 1
17 9 1 18
2 2 2 19
10 2 12 20
7 4 10 19
18 2 11 11
13 13 7 3
7 15 12 12
10 14 1 15
1 17 2 15
5 14 12 7
5 15 10 4
18 18 15 4
7 11 15 5
12 19 5 11
8 11 14 18
12 11 1 8
17 1 9 18
8 16 3 1
11 5 5 20
8 13 6 19
15 18 19 15
9 7 3 6
12 20 15 6
11 14 1 1
14 20 17 11
6 16 14 3
1 5 7 7
20 14 16 5
3 4 11 6
11 17 5 12
16 19 11 4
6 13 2 8
20 9 9 9
4 19 10 11
16 18 11 7
7 18 9 16
5 1 12 6
7 3 8 7
3 13 17 19
19 14 9 19
20 10 4 3
6 10 9 3
12 2 11 20
2 11 13 18
9 6 18 19
13 6 18 13
5 10 13 19
3 2 3 19
12 14 7 9
4 5 17 2
16 2 7 10
3 19 13 13
1 18 3 10

出力例2

2
DRRRULDUU-D-DUULRDUD-DDRUULDR-UUUDDR-UU-UUUD-LUDDUUDDUDUUDDUDDUDR-UD-U-U-DLDRDDRLLLU-RDDRU---UUDUDDU
DU-RULDUU-DRD-UDUDUD-LDRLULDRU-RULDDDURUUU-LRLUDDLULD-DUU-DUDD-DRLLDDUUUUD-DU-DR-L--URLRRURR-LUD-DRU

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

「入力ファイル」に問題の入力ファイルを、「出力ファイル」にあなたのプログラムの出力を保存したファイルを指定してください。

※入出力ファイルのサンプルはこちら

fps