ドラゴンのパズル

• H×Wマスのフィールド上に、1マスにつき1個のドロップが配置されている。
  • 座標は左上が (1, 1)、右下が (H, W)。
• ドロップの色は5種類あり、それぞれ1から5までの番号がついている。
• プレイヤーは「操作Aを1回行ったあと、操作BをM回以下行う」操作セットをN回以下行うことができる。
  • 操作A: フィールド上のドロップを1つ選択する。 (注意: マスではない)
    • 操作B: 操作Aで選択したドロップを、上下左右いずれかに移動する。移動した先のマス上のドロップは、移動元のマスと交換され移動する。
• フィールドの外にドロップを移動させることはでき内容を。
• 最終的になるべく同じ色のドロップが隣り合うように並び替えよ。

入力

H W N M
d11 d12 d13 ...
d21 d22 d23 ...
d31 d32 d33 ...
...

• 1行目に、H, W, N, M が空白区切りで与えられる。
• y + 1 (1 <= y <= H) 行目に、マス (x, y) 上のドロップの色 dix (1 <= dyx <= 5) が与えられる。
• フィールド上のドロップの5つの色はすべて同数含まれることが保証される。

出力

x1 x2
d11 d12 d13 d14 ...
x2 y2
d21 d22 d23 d24 ...
...

• i * 2 - 1 (1 <= i <= N) 行目に、i回目の操作セットの操作Aで選択するドロップが存在するマスの座標 (xi, yi) を空白区切りで出力せよ。
• i * 2 (1 <= i <= N) 行目に、i回目の操作セットのj回目の操作Bでドロップを移動させる方向dijを空白区切りで出力せよ。
  • 上 (-y方向) に移動: 1
  • 右 (+x方向) に移動: 2
  • 下 (+y方向) に移動: 3
  • 左 (-x方向) に移動: 4

スコア

• 最終的なフィールド上の、同じ色のドロップが隣接する領域全てについての、領域の大きさの二乗平均平方根 (RMS) がスコアとなる。

テストケース

• H = 5, W = 5, N = 3, M = 5 5ケース
• H = 10, W = 10, N = 10, M = 10 5ケース
• H = 20, W = 20, N = 30, M = 15 5ケース

サンプルコード

以下は、この問題に対して不正でない出力を行うC++のサンプルコードである。

#include <bits/stdc++.h>
using namespace std;

int **drops;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int H, W, N, M;
	cin >> H >> W >> N >> M;

	drops = (int **)malloc(sizeof(int *) * H);
	for (int y = 0; y < H; y++) {
		drops[y] = (int *)malloc(sizeof(int) * W);
		for (int x = 0; x < W; x++) {
			cin >> drops[y][x];
		}
	}

	for (int i = 0; i < N; i++) {
		cout << 2 << " " << 2 << endl;

		for (int j = 0; j < M; j++) {
			cout << (j % 4) + 1;
			if (j == M - 1) {
				cout << endl;
			} else {
				cout << " ";
			}
		}
	}

	return 0;
}

入力例

5 5 1 3
1 2 3 4 5
1 2 3 4 5
1 2 3 3 4
1 2 5 4 5
1 2 3 4 5

出力例

3 4
1 2 2