# 2. 题解

• 相同颜色的格子互换位置没有任何意义～
• （左移格子 X）与（右移 X 左边的那个格子）是等价的，且（右移 X 左边的那个格子）更优先
• 若某一种颜色的格子数目在 $[1,2]$中，则说明这个状态不可能有解。

QvQ

#include <bits/stdc++.h>

using namespace std;

int n;

bool bkr[5][7], bkc[5][7];

struct state
{
vector<int> d[5]; int col[11];
bool empty()
{
for (int i = 0; i < 5; i += 1)
if (!d[i].empty()) return 0;
return 1;
}
int clear()
{
memset(bkr, 0, sizeof(bkr)), memset(bkc, 0, sizeof(bkc));
for (int i = 0; i < 5; i += 1)
for (int j = 0; j < d[i].size(); j += 1)
if (!bkr[i][j])
{
int k = 1;
for (; k + i < 5; k += 1)
{
if (j >= d[k + i].size()) break;
if (d[k + i][j] != d[i][j]) break;
}
if (k >= 3) for (int l = 0; l < k; l += 1) bkr[l + i][j] = 1;
}
for (int i = 0; i < 5; i += 1)
for (int j = 0; j < d[i].size(); j += 1)
if (!bkc[i][j])
{
int k = 1;
for (; k + j < d[i].size(); k += 1)
if (d[i][k + j] != d[i][j]) break;
if (k >= 3) for (int l = 0; l < k; l += 1) bkc[i][l + j] = 1;
}
int res = 0;
for (int i = 0; i < 5; i += 1)
for (int j = d[i].size() - 1; j >= 0; j -= 1)
if (bkr[i][j] || bkc[i][j])
res++, col[d[i][j]]--, d[i].erase(d[i].begin() + j);
return res;
}
void move(int a, int b, int g)
{
if (g > 0)
{
if (d[a + 1].size() <= b)
{
d[a + 1].push_back(d[a][b]);
d[a].erase(d[a].begin() + b);
}
else swap(d[a][b], d[a + 1][b]);
}
else
{
if (d[a - 1].size() <= b)
{
d[a - 1].push_back(d[a][b]);
d[a].erase(d[a].begin() + b);
}
else swap(d[a][b], d[a - 1][b]);
}
while (clear());
}
} bgn, nxt;

int ans[10][3];

void Dfs(state s, int cnt)
{
if (cnt == n)
{
if (s.empty())
{
for (int i = 0; i < n; i += 1)
printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]);
exit(0);
}
return;
}
for (int i = 1; i <= 10; i += 1)
if (s.col[i] > 0 && s.col[i] <= 2) return;
for (int i = 0; i < 5; i += 1)
for (int j = 0; j < s.d[i].size(); j += 1)
{
if (i < 4)
{
if (s.d[i + 1].size() > j && s.d[i + 1][j] == s.d[i][j]) continue;
nxt = s, nxt.move(i, j, 1);
ans[cnt][0] = i, ans[cnt][1] = j, ans[cnt][2] = 1;
Dfs(nxt, cnt + 1);
}
if (i > 0 && s.d[i - 1].size() <= j)
{
nxt = s, nxt.move(i, j, -1);
ans[cnt][0] = i, ans[cnt][1] = j, ans[cnt][2] = -1;
Dfs(nxt, cnt + 1);
}
}
}
int main(int argc, char const* argv[])
{
scanf("%d", &n);
for (int i = 0, j; i < 5; i += 1)
while (scanf("%d", &j), j)
bgn.d[i].push_back(j), bgn.col[j]++;
Dfs(bgn, 0), puts("-1");
return 0;
}