HDU - 1430 魔板 (bfs预处理 + 康托)

对于该题可以直接预处理初始状态[0, 1, 2, 3, 4, 5, 6, 7]所有可以到达的状态，保存到达的路径，直接打印答案即可。

关于此处的状态转换：假设有初始状态为2,3,4,5,0,6,7,1，目标状态为7,1,4,5,2,3,0,6，首先把初态看做0,1,2,3,4,5,6,7，那么目标状态应该看做6,7,2,3,0,1,4,5直接查询到达状态6,7,2,3,0,1,4,5的路径即可。

PS：hdu3567与这题类似。

AC代码：93ms

#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
typedef int state[8];
const int maxn = 45000;

int vis[maxn];
string path[maxn];

int op[][8] = {
	4, 5, 6, 7, 0, 1, 2, 3,
	3, 0, 1, 2, 7, 4, 5, 6,
	0, 5, 1, 3, 4, 6, 2, 7
};

char dir[] = {'A', 'B', 'C'};

int st[] = {0, 1, 2, 3, 4, 5, 6, 7};

int fact[8];
void deal() {  //1~8阶乘打表，方便编码
	fact[0] = 1;
	for(int i = 1; i < 8; ++i) fact[i] = fact[i - 1] * i;
}

int KT(int *a) { //康托
	int code = 0;
	for(int i = 0; i < 8; ++i) {
		int cnt = 0;
		for(int j = i + 1; j < 8; ++j) if(a[j] < a[i]) cnt++;
		code += fact[7 - i] * cnt;
	}
	return code;
} 

struct node{
	int a[8];
	int code;
	node(){
	}
	node(int *b, int code):code(code) {
		memcpy(a, b, sizeof(a));
	}
};

void walk(int c, int *a) { //对数组进行第c种操作
	int b[8];
	memcpy(b, a, sizeof(b));
	for(int i = 0; i < 8; ++i) {
		a[i] = b[op[c][i]];
	}
}

void bfs() {  //预处理所有可以到达的状态
	memset(vis, 0, sizeof(vis));
	int code = KT(st);
	vis[code] = 1;
	path[code] = "";
	queue<node>q;
	q.push(node(st, code));
	while(!q.empty()){
		node p = q.front();
		q.pop();
		int a[8];
		for(int i = 0; i < 3; ++i) { //三种操作
			memcpy(a, p.a, sizeof(a));
			walk(i, a);
			code = KT(a);
			if(!vis[code]) {
				vis[code] = 1;
				path[code] = path[p.code] + dir[i];
				q.push(node(a, code));
			}
		}
	}
}

void deal(int *a) {
	swap(a[4], a[7]);
	swap(a[5], a[6]);
}

int main() {
	deal();
	bfs();
	int a[8], b[8], ha[8];
	char s[20];
	while(scanf("%s", s) == 1) {
		for(int i = 0; i < 8; ++i) {
			a[i] = s[i] - '0' - 1;
		}
		deal(a);
		for(int i = 0; i < 8; ++i) {
			ha[a[i]] = i;
		}
		scanf("%s", s);
		for(int i = 0; i < 8; ++i) {
			b[i] = s[i] - '0' - 1;
		}
		deal(b);
		for(int i = 0; i < 8; ++i) a[i] = ha[b[i]];
		int code = KT(a);
		cout << path[code] << endl;
		//cout << "HELLO" <<endl;
	}

	return 0;
}

如有不当之处欢迎指出！

巴特西

HDU - 1430 魔板 (bfs预处理 + 康托)

最新文章

热门文章