bfsTLE求调
  • 板块P5507 机关
  • 楼主yezicong1104
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/9 19:11
  • 上次更新2024/11/9 21:16:47
查看原帖
bfsTLE求调
1046228
yezicong1104楼主2024/11/9 19:11
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

int dis[1 << 24], s[12], a[12][4], x, pre[1 << 24], fa[1 << 24];

void print(int n) {
	if (!dis[n]) return;
	print(pre[n]);
	cout << fa[n] + 1 << ' ';
}

int main() {
	for (int i = 0; i < 12; i++) {
		cin >> s[i];
		x = x * 4 + s[i] - 1;
		for (int j = 0; j < 4; j++) cin >> a[i][j], a[i][j]--;
	}

	queue<int> q;
	q.push(x);
	memset(dis, -1, sizeof(dis));
	dis[x] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (!u) break;
		for (int i = u, j = 0, k = 11; j < 12; i /= 4, j++, k--) {
			int t = a[k][i % 4], g = 11 - t, y = u >> 2 * g;
			int x1 = i % 4, y1 = (i % 4 + 1) % 4;
			int x2 = y % 4, y2 = (y % 4 + 1) % 4;
			int v = u + (1 << 2 * j) * (y1 - x1) + (1 << 2 * g) * (y2 - x2);
			if (dis[v] == -1) {
				q.push(v);
				dis[v] = dis[u] + 1, pre[v] = u, fa[v] = k;
			}
		}
	}

	cout << dis[0] << endl;
	print(0);
	return 0;
}
2024/11/9 19:11
加载中...