代码

P1379 八数码难题(康托展开+逆展开+我的丑陋的BFS)

[infobox title="P1379 八数码难题 "]
题目描述

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。
输入输出格式
输入格式:

输入初试状态,一行九个数字,空格用0表示

输出格式:

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

输入输出样例
输入样例#1:

283104765

输出样例#1:

4

https://www.luogu.org/problem/show?pid=1379
[/infobox]
我的做法:
BFS不是难事,关键是记录状态和判重,要用到一个叫康托展开的哈希函数还有其逆展开..
大致思路就是把初始状态的康托展开计算出来推入队列,然后将其逆展开,交换与0相邻的元素,分别算出他们的康托展开再推入队列..
然而就是这么猥琐+丑陋又不加剪枝的算法竟然A了..
附上代码..

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define MAXN 400000
#define INF 0x3f3f3f3f
using namespace std;
char s[10];
int fac[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362840, 3628400};//get the value before hand
int step[MAXN];
int vis[MAXN];
int a[9];
int cantor(char* a){
	int can = 0;
	for (int i = 0; i < 9; i++){
		int tmp = 0;
		for (int j = i + 1; j < 9; j++)
			if (a[j] < a[i]) tmp++;
		can += tmp * fac[9 - i - 1];
	}

	return can;
}

void uncantor(int a, char* s){
	int used[10] = {0};
	int j, t;
	for (int i = 0; i < 9; i++){
		t = a / fac[9 - i - 1];
		for (j = 1; j <= 9; j++){
			if (!used[j]){
				if (t == 0) break;
				t--;
			}
		}
		s[i] = '0' + j - 1;
		used[j] = 1;
		a %= fac[9 - i - 1];
	}
}
int main(){
	scanf("%s", s);
	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < MAXN; i++) step[i] = INF;
	step[cantor(s)] = 0;
//	cout << cantor(s) << endl;
//	uncantor(cantor(s), s);
//	cout << s << endl;
	queue<int> q;
	q.push(cantor(s));
	int zr = 0;//The pos of '0'
	int now, nc;
	char tp[9];
	while(!q.empty()){
		now = q.front();
		q.pop();
//		cout << now << endl;
		uncantor(now, tp);
		vis[now] = 1;
		for (int i = 0; i < 9; i++) if(tp[i] == '0') zr = i;
		if (zr > 2) {//up
			swap(tp[zr], tp[zr - 3]);
			nc = cantor(tp);
			step[nc] = min(step[nc], step[now] + 1);
			if (!vis[nc]) q.push(nc);
			swap(tp[zr], tp[zr - 3]);
		}
		if (zr < 6) {//down
			swap(tp[zr], tp[zr + 3]);
			nc = cantor(tp);
			step[nc] = min(step[nc], step[now] + 1);
			if (!vis[nc]) q.push(nc);
			swap(tp[zr], tp[zr + 3]);
		}
		if (zr % 3 != 0) {//left
			swap(tp[zr], tp[zr - 1]);
			nc = cantor(tp);
			step[nc] = min(step[nc], step[now] + 1);
			if (!vis[nc]) q.push(nc);
			swap(tp[zr], tp[zr - 1]);
		}
		if (zr % 3 != 2) {//right
			swap(tp[zr], tp[zr + 1]);
			nc = cantor(tp);
			step[nc] = min(step[nc], step[now] + 1);
			if (!vis[nc]) q.push(nc);
			swap(tp[zr], tp[zr + 1]);
		}
	}
	cout << step[46685] << endl;//the hash of '123804765'(the final state) is 46685 = =!
}

第一次用到哈希??

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐