悬关,90pts(o2的问题?)
查看原帖
悬关,90pts(o2的问题?)
520544
Phrvth楼主2023/6/10 22:07

哪位大佬莅临人间

我捉摸着我的代码和题解差不多啊,怎么这么慢?

#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;
}
2023/6/10 22:07
加载中...