原题链接
讨厌这种大搜索题
基本就是模拟搜索，注意细节即可。
以下是我用的两个剪枝：
- 将块向左移的前提是左边为空，因为该题要求先右后左，所以若左边有块，那么在上一次搜索向右移的时候一定会搜过，且字典序更小。
- 对每次搜索的图进行\(HASH\)储存，即记忆化。
表示这题把我\(HASH\)卡了。。最后乱改\(base\)，改成\(131\times 1331\)的时候终于过了。。
所以我的代码还是有一定可能性被卡掉的，不过其实只需加第一个剪枝就能通过此题，只不过跑的比较慢（说不定不剪枝也能过，并没有测试过）。
另外，该题还可以加另一个剪枝：若当前状态中有一种块的数量为\(1\)或\(2\)，则该状态定无法消去所有块，直接返回。
这里我并没有用该剪枝（感觉并没有必要）。
代码又臭又长
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 10;
const int mod = 999983;
struct cdr {
int x, y, z, p;
cdr()
{
x = y = z = p = 0;
}
};
struct dd {
int x, y, z;
};
dd an[N];
int o[N][N], f[N << 2], v[mod + 10], n, p, ma_co;
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
inline void sw(int &x, int &y)
{
int z = x;
x = y;
y = z;
}
int sch_rem(int x, int y, int co, int b[N][N], int l[])
{
int i, s_1 = 1, s_2 = 1;
for (i = y + 1; i <= l[x]; i++)
if (b[x][i] ^ co)
break;
else
s_1++;
for (i = y - 1; i; i--)
if (b[x][i] ^ co)
break;
else
s_1++;
for (i = x + 1; i < 6; i++)
if (b[i][y] ^ co)
break;
else
s_2++;
for (i = x - 1; i; i--)
if (b[i][y] ^ co)
break;
else
s_2++;
if (s_1 > 2 && s_2 > 2)
{
p = 3;
return s_1 + s_2 - 1;
}
if (s_1 > 2)
{
p = 1;
return s_1;
}
if (s_2 > 2)
{
p = 2;
return s_2;
}
return 0;
}
void rem(int x, int y, int hw, int co, int b[N][N], int l[])
{
int i;
b[x][y] = 0;
if (hw ^ 2)
{
for (i = y + 1; i <= l[x]; i++)
if (b[x][i] ^ co)
break;
else
b[x][i] = 0;
for (i = y - 1; i; i--)
if (b[x][i] ^ co)
break;
else
b[x][i] = 0;
}
if (hw ^ 1)
{
for (i = x + 1; i < 6; i++)
if (b[i][y] ^ co)
break;
else
b[i][y] = 0;
for (i = x - 1; i; i--)
if (b[i][y] ^ co)
break;
else
b[i][y] = 0;
}
}
void downbk(int b[N][N], int l[])
{
int i, j, k;
for (i = 1; i < 6; i++)
{
for (j = 1; j <= l[i]; j++)
if (!b[i][j])
break;
for (k = j + 1; k <= l[i]; k++)
if (b[i][k])
break;
if (j <= l[i] && k <= l[i])
for (; k <= l[i]; k++)
{
b[i][j++] = b[i][k];
b[i][k] = 0;
}
l[i] = j - 1;
}
}
int mkhs(int b[N][N])
{
int i, j, k = -1, s = 0;
for (i = 1; i < 6; i++)
for (j = 1; j < 8; j++)
{
k++;
s = (s + 1LL * f[k] * (b[i][j] + 1) % mod) % mod;
}
return s;
}
int try_rem(cdr S[], int b[N][N], int l[])
{
int i, j, s = 0, k;
bool fg = 1;
while (fg)
{
fg = 0;
for (i = 1; i < 6; i++)
for (j = 1; j <= l[i]; j++)
if (S[b[i][j]].z < (k = sch_rem(i, j, b[i][j], b, l)))
{
S[b[i][j]].z = k;
S[b[i][j]].p = p;
S[b[i][j]].x = i;
S[b[i][j]].y = j;
}
for (i = 1; i <= ma_co; i++)
if (S[i].z > 2)
{
rem(S[i].x, S[i].y, S[i].p, i, b, l);
fg = 1;
s += S[i].z;
S[i].z = 0;
}
if (fg)
downbk(b, l);
}
return s;
}
bool dfs(int nw, int la, int a[N][N])
{
int b[N][N], l[N], i, j, k, s;
cdr S[N + 3];
memset(b, 0, sizeof(b));
memset(l, 0, sizeof(l));
for (i = 1; i < 6; i++)
{
for (j = 1; j < 8; j++)
b[i][j] = a[i][j];
l[i] = 7;
}
downbk(b, l);
s = try_rem(S, b, l);
if (nw > n)
{
if (la ^ s)
return false;
return true;
}
for (i = 1; i < 6; i++)
for (j = 1; j <= l[i]; j++)
{
if (i < 5)
{
sw(b[i][j], b[i + 1][j]);
k = mkhs(b);
if (v[k] > nw)
{
v[k] = nw;
if (dfs(nw + 1, la - s, b))
{
an[nw].x = i - 1;
an[nw].y = j - 1;
an[nw].z = 1;
return true;
}
}
sw(b[i][j], b[i + 1][j]);
}
if (i > 1 && !b[i - 1][j])
{
sw(b[i][j], b[i - 1][j]);
k = mkhs(b);
if (v[k] > nw)
{
v[k] = nw;
if (dfs(nw + 1, la - s, b))
{
an[nw].x = i - 1;
an[nw].y = j - 1;
an[nw].z = -1;
return true;
}
}
sw(b[i][j], b[i - 1][j]);
}
}
return false;
}
int main()
{
int i, j, s = 0;
n = re();
memset(v, 60, sizeof(v));
for (f[0] = i = 1; i < 36; i++)
f[i] = 1LL * f[i - 1] * 1331 % mod * 131 % mod;
for (i = 1; i < 6; i++)
for (j = 1; ; j++)
{
o[i][j] = re();
ma_co = maxn(ma_co, o[i][j]);
if (!o[i][j])
{
s += j - 1;
break;
}
}
v[mkhs(o)] = 1;
if (!dfs(1, s, o))
printf("-1");
else
for (i = 1; i <= n; i++)
printf("%d %d %d\n", an[i].x, an[i].y, an[i].z);
return 0;
}