哪位大佬莅临人间
我捉摸着我的代码和题解差不多啊,怎么这么慢?
#include <bits/stdc++.h>
using namespace std;
const int n = 5, m = 7;
int f;
struct Node {
int A[n + 7][m + 7], B[n + 7][n + 7][m + 7];//回溯用
void copy(int x) {
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
B[x][i][j] = A[i][j];
}
void update() {//处理掉下去操作
for (int i = 1; i <= n; i ++) {
int x = 0;
for (int j = 1; j <= m; j ++) {
if (!A[i][j]) x ++;
else swap(A[i][j - x], A[i][j]);
}
}
}
bool isin(int x, int y) {//判断是否出界
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
bool three(int a, int b, int c) {//三数是否相等
return a == b && a == c;
}
void print() {
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
cout << A[i][j] << (j == m ? '\n' : ' ');
cout << '\n';
}
bool remove() {//消除操作
int rm[n + 7][m + 7] = {0};//消除数组
int flag = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
if (A[i][j]) {
if (isin(i - 1, j) && isin(i + 1, j) && three(A[i - 1][j], A[i][j], A[i + 1][j])) {
rm[i - 1][j] = 1, rm[i][j] = 1, rm[i + 1][j] = 1;
flag = 1;
} else if(isin(i, j - 1) && isin(i, j + 1) && three(A[i][j - 1], A[i][j], A[i][j + 1])) {
rm[i][j - 1] = 1, rm[i][j] = 1, rm[i][j + 1] = 1;
flag = 1;
}
}
}
if (!flag) return false;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++) {
if (rm[i][j]) A[i][j] = 0;
}
return true;
}
void move(int x, int y, int k) {//将x移动k各单位
int xx = x + k, yy = y;
swap(A[x][y], A[xx][yy]);
update();
while (remove()) update();
}
bool check() {
for (int i = 1; i <= n; i ++)
if (A[i][1]) return false;
return true;
}
}a;
int Ans[n + m][3], ansn;
void dfs(int x) {
if (a.check()) {
for (int i = 1; i <= ansn; i ++) {
cout << Ans[i][0] << ' ' << Ans[i][1] << ' ' << Ans[i][2] << '\n';
}
exit(0);//结束
}
if (x > f) {return ;}
a.copy(x);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (a.A[i][j]) {
//往下移动
int xx = i + 1, yy = j;
if (a.isin(xx, yy) && a.A[xx][yy] != a.A[i][j]) {
a.move(i, j, 1);
Ans[x][0] = i - 1, Ans[x][1] = j - 1, Ans[x][2] = 1; ansn ++;
dfs(x + 1);
Ans[x][0] = -1, Ans[x][1] = -1, Ans[x][2] = -1; ansn --;
for (int q = 1; q <= n; q ++) for (int w = 1; w <= m; w ++) {
a.A[q][w] = a.B[x][q][w];
}
}
//往上移动
xx = i - 1, yy = j;
if (a.isin(xx, yy) && !a.A[xx][yy]) {
a.move(i, j, -1);
Ans[x][0] = i - 1, Ans[x][1] = j - 1, Ans[x][2] = -1; ansn ++;
dfs(x + 1);
Ans[x][0] = -1, Ans[x][1] = -1, Ans[x][2] = -1; ansn --;
for (int q = 1; q <= n; q ++) for (int w = 1; w <= m; w ++) {
a.A[q][w] = a.B[x][q][w];
}
}
}
}
}
}
int main () {
cin >> f;
for (int i = 1; i <= n; i ++) {
int cnt = 0, x;
while (cin >> x) {
if (x == 0) break;
a.A[i][++ cnt] = x;
}
a.A[i][0] = cnt;
}
dfs(1);
cout << -1 << '\n';
return 0;
}