传送门
Luogu
解题思路
爆搜，并考虑几个剪枝。
- 不交换颜色相同的方块（有争议，但是可以过联赛数据 \(Q \omega Q\)）
- 左边为空才往左换
- 右边不为空才往右换
因为对于两个相邻方块，右边往左换和左边往右换是等价的，同时还可以保证字典序最小。
细节注意事项
- 爆搜题，你们懂的。。。
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
int n, a[10][10], la[10][10][10], ans[10][10], mark[10][10];
inline bool remv() {
int flag = 0;
for (rg int i = 1; i <= 5; ++i)
for (rg int j = 1; j <= 7; ++j)
if (a[i][j]) {
if (i > 1 && i < 5 && a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j])
flag = 1, mark[i][j] = mark[i - 1][j] = mark[i + 1][j] = 1;
if (j > 1 && j < 7 && a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1])
flag = 1, mark[i][j] = mark[i][j - 1] = mark[i][j + 1] = 1;
}
if (!flag) return 0;
for (rg int i = 1; i <= 5; ++i)
for (rg int j = 1; j <= 7; ++j)
if (mark[i][j])
mark[i][j] = 0, a[i][j] = 0;
return 1;
}
inline void upt() {
for (rg int i = 1; i <= 5; ++i) {
int s = 0;
for (rg int j = 1; j <= 7; ++j) {
if (!a[i][j]) ++s;
else if (s) a[i][j - s] = a[i][j], a[i][j] = 0;
}
}
}
inline void mv(int i, int j, int t) {
swap(a[i][j], a[i + t][j]);
do { upt(); } while (remv());
}
inline bool check() {
for (rg int i = 1; i <= 5; ++i)
if (a[i][1]) return 0;
return 1;
}
inline void dfs(int x) {
if (check()) {
for (rg int i = 1; i < x; ++i)
printf("%d %d %d\n", ans[0][i], ans[1][i], ans[2][i]);
exit(0);
}
if (x > n) return;
memcpy(la[x], a, sizeof a);
for (rg int i = 1; i <= 5; ++i)
for (rg int j = 1; j <= 7; ++j)
if (a[i][j]) {
if (i < 5 && a[i + 1][j] != a[i][j]) {
mv(i, j, 1);
ans[0][x] = i - 1, ans[1][x] = j - 1, ans[2][x] = 1;
dfs(x + 1);
memcpy(a, la[x], sizeof la[x]);
ans[0][x] = 0, ans[1][x] = 0, ans[2][x] = 0;
}
if (i > 1 && a[i - 1][j] == 0) {
mv(i, j, -1);
ans[0][x] = i - 1, ans[1][x] = j - 1, ans[2][x] = -1;
dfs(x + 1);
memcpy(a, la[x], sizeof la[x]);
ans[0][x] = 0, ans[1][x] = 0, ans[2][x] = 0;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n);
for (rg int i = 1; i <= 5; ++i)
for (rg int j = 1; j <= 8; ++j) {
read(a[i][j]); if (a[i][j] == 0) break;
}
dfs(1);
puts("-1");
return 0;
}
完结撒花 \(qwq\)