ドラゴンのパズル
- 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
Submit Code