2019-09-13

hdu 1043 Eight 八数码康托展开+搜索

缘起

搜索经典问题——“八数码” hdu 1043 Eight

分析

就是给你一串例如  1 2 3 x 4 6 7 5 8 表示
1 2 3
x 4 6
7 5 8
要你给出操作序列将上面的矩阵变成
1 2 3
4 5 6
7 8 x
如果无解的话, 输出 "unsolvable"

【输入】
多样例, 每个样例给你一串

【输出】
每个样例要么输出解（任何一组解都行）

【样例输入】
2  3  4  1  5  x  7  6  8

【样例输出】
ullddrurdllurdruldr

【限制】
5s

本题将采用 BFS、DBFS（双向BFS）、A* 三种搜索算法来做. 当然，因为死去的节点不需要复活，所以必须要对这些节点进行哈希. 则康托展开就成为极好的选择（见【2】）.

注意，因为本题没有限制搜索的次数. 所以使用IDA*是不合适的. 应该使用宽度类型的搜索算法.

bfs姿势

代码没什么好说的~ bfs唯一要注意的事情是, 队列用指针队列最稳妥不会出错~

//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

char a[9];
bool v[362880]; // 用康托函数来哈希所有的全排列
const int dir[4][2] ={{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右四个方向

struct Node // 队列中的节点
{
	char b[3][3], move; // 当前棋盘, move取值u/d/l/r（上下左右）, 表示是如何移动到此节点的
	int x,y; // 'x'所在的行和列
	Node *prev; // 由谁开拓的
};

bool read()
{
	int num = 1;
	while(num<=8)
	{
		char c = getchar();
		if (c==' '|| c=='\n')
		{
			continue;
		}
		a[num] = c;
		num++;
	}
	int rev = 0; // 原序列（除了'x'）的逆序数
	for (int i = 0; i<8; i++)
	{
		for (int j = i+1; j<9; j++)
		{
			if (a[i]!='x'&&a[i]>a[j])
			{
				rev++;
			}
		}
	}
	return rev&1;
}

int cantor(char b[3][3]) // 计算节点的数组的cantor展开(其实就是9!)
{
	int bb[9];
	for (int i = 0;i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (b[i][j]=='x') // 将'x'视作9
			{
				bb[3*i+j] = 9;
			}
			else
			{
				bb[3*i+j] = b[i][j]-'0';
			}
		}
	}
	int fac = 40320; // 8!
	int ans = 0;
	bool vv[10];
	memset(vv, 0, sizeof(vv));
	int t[9];
	for (int i = 0; i<9; i++)
	{
		t[i] = 0;
		for (int j = 1; j<bb[i]; j++) // 找 bb[i]之前没有出现的数的个数
		{
			if (!vv[j])
			{
				t[i]++;
			}
		}
		vv[bb[i]] = true;
		ans+=t[i]*fac;
		if (i<8)
		{
			fac/=(8-i);
		}
	}
	return ans;
}

bool ok(Node n) // 一个节点是不是达到终点了
{
	if (n.b[2][2]!='x')
	{
		return false;
	}
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (i==2&&j==2)
			{
				continue;
			}
			if (n.b[i][j]-'0'!=3*i+j+1)
			{
				return false;
			}
		}
	}
	return true;
}

void printsol(Node *front) // 递归打印解
{
	if (front->prev)
	{
		printsol(front->prev);
	}
	if (front->prev) // 是从某个节点移动得来的才有move
	{
		putchar(front->move);
	}
}

void bfs()
{
	memset(v, 0, sizeof(v));
	queue<Node*> q; // 记住, bfs队列里面最好存指针, 这样万无一失!
	Node *first = new Node;
	first->prev = 0;
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			first->b[i][j] = a[3*i+j];
			if (a[3*i+j] == 'x')
			{
				first->x = i;
				first->y = j;
			}
		}
	}
	q.push(first);
	v[cantor(first->b)] = true; // 哈希判重
	Node *front;
	while(!q.empty())
	{
		front = q.front();
		if (ok(*front))
		{
			break;
		}
		q.pop();
		for (int i = 0,nx,ny; i<4; i++) // 沿着四个方向拓展节点
		{
			nx = front->x+dir[i][0];
			ny = front->y+dir[i][1];
			if (nx<0||nx>2||ny<0||ny>2) // 如果越界了
			{
				continue;
			}
			// 则交换top.b[x][y]和top.b[nx][ny]
			swap(front->b[front->x][front->y], front->b[nx][ny]);
			int tc = cantor(front->b); // 试探交换后的哈希值
			if (v[tc])
			{
				swap(front->b[front->x][front->y], front->b[nx][ny]); // 交换回来(因为top.b不能变)
				continue;
			}
			Node *n = new Node; // 如果开拓的状态并没有使用
			n->x = nx, n->y = ny;
			switch(i)
			{
			case 0:
				n->move = 'u';
				break;
			case 1:
				n->move = 'd';
				break;
			case 2:
				n->move = 'l';
				break;
			case 3:
				n->move = 'r';
				break;
			default:
				break;
			}
			memcpy(n->b, front->b, sizeof(n->b));
			n->prev = front;
			swap(front->b[front->x][front->y], front->b[nx][ny]); // 交换回来(因为top.b不能变)
			q.push(n);
			v[tc] = true;
		}
	}
	if (q.empty())
	{
		puts("unsolvable");
	}
	else
	{
		printsol(front); // 打印解
		puts("");
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%c", a))
	{
		if (read()) // 如果除了'x'的原序列的逆序数为奇数的话, 则必定无解. 注意, 如果对于无解情形你还去搜的话, 哪怕是A*也会被T, 因为要遍历所有的节点(而且还没有结果).效率很低的
		{
			puts("unsolvable");
			continue;
		}
		bfs();
		getchar();// 吸收尾部换行符
	}
	return 0;
}

ac情况（但是我是在 poj 1077 Eight 上ac的, 因为那题内存比较充裕(但是时间限制在1s, 所以真的好危险~). 但是在hdu 1043 上跑就MLE了~ 咳咳咳~ 懒得优化了）

Status	Accepted
Time	938ms
Memory	9276kB
Length	3387
Lang	C++
Submitted	2019-09-18 09:11:29
Shared
RemoteRunId	20870400

多说一句, 其实（单向）bfs还挺快~ 嘿嘿~

DBFS姿势

双向bfs（DBFS），它的思想是从初始状态和目标状态同时出发进行bfs. 一旦在中间交汇的话, 则就判定出现了一组解. 为什么DBFS会比bfs快呢? 一图胜千言

上面的单向bfs姿势搜索的节点是S1+S2+S3, 而dbfs搜索的节点是S1. 也就是单向bfs搜索的范围会比dbfs多出两块S2+S3来. 所以DBFS会比BFS效率高的多

//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

char a[9];
bool v1[362880],v2[362880];
const int dir[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};
struct Node // 队列中的节点
{
	char b[3][3], move; 
	int x,y; 
	Node *prev;
};
queue<Node *> q1,q2; // q1用于跑正向bfs, q2用于跑逆向bfs

Node *vn1[362880], *vn2[362880]; // 用于记录某个Node节点的地址

bool read()
{
	int num = 1;
	while(num<=8)
	{
		char c = getchar();
		if (c==' '|| c=='\n')
		{
			continue;
		}
		a[num] = c;
		num++;
	}
	int rev = 0; 
	for (int i = 0; i<8; i++)
	{
		for (int j = i+1; j<9; j++)
		{
			if (a[i]!='x'&&a[i]>a[j])
			{
				rev++;
			}
		}
	}
	return rev&1;
}

int cantor(char b[3][3]) 
{
	int bb[9];
	for (int i = 0;i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (b[i][j]=='x') 
			{
				bb[3*i+j] = 9;
			}
			else
			{
				bb[3*i+j] = b[i][j]-'0';
			}
		}
	}
	int fac = 40320;
	int ans = 0;
	bool vv[10];
	memset(vv, 0, sizeof(vv));
	int t[9];
	for (int i = 0; i<9; i++)
	{
		t[i] = 0;
		for (int j = 1; j<bb[i]; j++) 
		{
			if (!vv[j])
			{
				t[i]++;
			}
		}
		vv[bb[i]] = true;
		ans+=t[i]*fac;
		if (i<8)
		{
			fac/=(8-i);
		}
	}
	return ans;
}

void init1()
{
	while(!q1.empty())q1.pop();
	Node *first = new Node;
	first->prev = 0;
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			first->b[i][j] = a[3*i+j];
			if (a[3*i+j] == 'x')
			{
				first->x = i;
				first->y = j;
			}
		}
	}
	q1.push(first);
	int vcantor = cantor(first->b);
	v1[vcantor] = true;
	vn1[vcantor] = first;
}

void init2()
{
	while(!q2.empty())q2.pop();
	Node *first = new Node;
	first->prev = 0;
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (i==2&&j==2)
			{
				continue;
			}
			first->b[i][j] = 3*i+j+'1';
		}
	}
	first->b[2][2]='x';
	first->x = first->y = 2;
	q2.push(first);
	int vcantor = cantor(first->b);
	v2[vcantor] = true;
	vn2[vcantor] = first; // 这里是有漏洞的, 因为如果一开始就是终态的话~ 但是我赌题目不会有这样的测试数据
}

void printsol1(Node *p) // 递归打印(前半部分)解
{
	if (p->prev)
	{
		printsol1(p->prev);
	}
	if (p->prev)
	{
		putchar(p->move);
	}
}

char transf(char move) // 因为反向bfs返回的方向要是反的
{
	switch(move)
	{
	case 'u':
		return 'd';
	case 'd':
		return 'u';
	case 'l':
		return 'r';
	case 'r':
		return 'l';
	}
}

void printsol(Node *node1, Node *node2) // 打印解, node1是正向bfs队列中的节点, node2是反向bfs队列中的节点
{
	printsol1(node1); // 打印前半部分
	while(node2->prev)
	{
		putchar(transf(node2->move));
		node2 = node2->prev;
	}
}

void dbfs() // 双向bfs搜索
{
	memset(v1, 0, sizeof(v1));
	memset(v2, 0, sizeof(v2));
	init1(); // 初始化q1
	init2(); // 初始化q2
	Node *front1, *front2;
	while(!q1.empty()||!q2.empty()) //如果q1和q2至少一个不是空
	{
		if (!q1.empty())
		{
			front1 =  q1.front();
			int vcantor = cantor(front1->b);
			if (v2[vcantor]) // 如果反向bfs搜到过这个节点的话
			{
				front2 = vn2[vcantor]; // 找到和正向bfs接头的那个反向bfs节点
				break;
			}
			q1.pop(); // 开拓节点了
			for (int i = 0,nx,ny; i<4; i++)
			{
				nx = front1->x+dir[i][0];
				ny = front1->y+dir[i][1];
				if (nx<0||nx>2||ny<0||ny>2)
				{
					continue;
				}
				swap(front1->b[front1->x][front1->y], front1->b[nx][ny]);
				int tc = cantor(front1->b);
				if (v1[tc])
				{
					swap(front1->b[front1->x][front1->y], front1->b[nx][ny]); 
					continue;
				}
				Node *n = new Node;
				n->x = nx, n->y = ny;
				switch(i)
				{
				case 0:
					n->move = 'u';
					break;
				case 1:
					n->move = 'd';
					break;
				case 2:
					n->move = 'l';
					break;
				case 3:
					n->move = 'r';
					break;
				default:
					break;
				}
				memcpy(n->b, front1->b, sizeof(n->b));
				n->prev = front1;
				swap(front1->b[front1->x][front1->y], front1->b[nx][ny]); 
				q1.push(n);
				v1[tc] = true;
				vn1[tc] = n;
			}
		}
		if (!q2.empty())
		{
			front2 = q2.front();
			int vcantor = cantor(front2->b);
			if (v1[vcantor]) // 如果正向bfs搜到过这个节点的话
			{
				front1 = vn1[vcantor]; // 找到和反向bfs接头的那个正向bfs节点
				break;
			}
			q2.pop(); // 开拓节点了
			for (int i = 0,nx,ny; i<4; i++)
			{
				nx = front2->x+dir[i][0];
				ny = front2->y+dir[i][1];
				if (nx<0||nx>2||ny<0||ny>2)
				{
					continue;
				}
				swap(front2->b[front2->x][front2->y], front2->b[nx][ny]);
				int tc = cantor(front2->b);
				if (v2[tc])
				{
					swap(front2->b[front2->x][front2->y], front2->b[nx][ny]); 
					continue;
				}
				Node *n = new Node;
				n->x = nx, n->y = ny;
				switch(i)
				{
				case 0:
					n->move = 'u';
					break;
				case 1:
					n->move = 'd';
					break;
				case 2:
					n->move = 'l';
					break;
				case 3:
					n->move = 'r';
					break;
				default:
					break;
				}
				memcpy(n->b, front2->b, sizeof(n->b));
				n->prev = front2;
				swap(front2->b[front2->x][front2->y], front2->b[nx][ny]); 
				q2.push(n);
				v2[tc] = true;
				vn2[tc] = n;
			}
		}
	}
	if (q1.empty()&&q2.empty()) // 如果都搜空了
	{
		puts("unsolvable");
	}
	else
	{
		printsol(front1, front2); // front1和front2是接上头的两个节点. 其中front1是正向bfs的节点, front2是反向bfs的节点
		puts("");
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%c", a))
	{
		if (read()) 
		{
			puts("unsolvable");
			continue;
		}
		dbfs();
		getchar();
	}
	return 0;
}

ac情况（很惭愧的说——依旧是在poj上ac的, hdu上报RE~）而且 dbfs使用的内存差不多就是单向bfs的一半. 而且性能快的飞起（差不多提高了10倍的效率）~ 嘿嘿~ 第一次写 DBFS~

Status	Accepted
Time	94ms
Memory	4348kB
Length	5124
Lang	C++
Submitted	2019-09-18 12:27:23
Shared
RemoteRunId	20870813

A*姿势

因为要使用A*姿势,势必需要选择合适的启发式函数. 这里对于一种状态而言, 选择的启发式函数是到达目标位置的曼哈顿距离之和. 什么意思呢? 例如

1
2
3

8 6 7
2 5 4
3 x 1

则8本应该在第2行第1列的，但是现在在第0行第0列, 则曼哈顿距离就是

1	\|2-0\|+\|1-0\|=3

逐个考察3*3矩阵中的每个数, 求曼哈顿距离之和就是启发式函数.

//#include "stdafx.h"

#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL
#define ABS(a,b) ((a)>(b)?((a)-(b)):((b)-(a)))

char a[9];
bool v[362880];
const int dir[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};

struct Node 
{
	char b[3][3], move; 
	int x,y;
	Node *prev;
	int g,h; // g是迄今为止的真实代价函数, h是启发式函数
};

int h(Node *p) // 计算节点的启发式函数
{
	int ans = 0;
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (p->b[i][j]=='x') // 不需要计算x的, 因为1~8归位了, x自然归位了
			{
				continue;
			}
			ans+=ABS(i, (p->b[i][j]-'1')/3)+ ABS(j, (p->b[i][j]-'1')%3); // 曼哈顿距离
		}
	}
	return ans;
}

bool read()
{
	int num = 1;
	while(num<=8)
	{
		char c = getchar();
		if (c==' '|| c=='\n')
		{
			continue;
		}
		a[num] = c;
		num++;
	}
	int rev = 0; 
	for (int i = 0; i<8; i++)
	{
		for (int j = i+1; j<9; j++)
		{
			if (a[i]!='x'&&a[i]>a[j])
			{
				rev++;
			}
		}
	}
	return rev&1;
}

int cantor(char b[3][3])
{
	int bb[9];
	for (int i = 0;i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (b[i][j]=='x')
			{
				bb[3*i+j] = 9;
			}
			else
			{
				bb[3*i+j] = b[i][j]-'0';
			}
		}
	}
	int fac = 40320;
	int ans = 0;
	bool vv[10];
	memset(vv, 0, sizeof(vv));
	int t[9];
	for (int i = 0; i<9; i++)
	{
		t[i] = 0;
		for (int j = 1; j<bb[i]; j++)
		{
			if (!vv[j])
			{
				t[i]++;
			}
		}
		vv[bb[i]] = true;
		ans+=t[i]*fac;
		if (i<8)
		{
			fac/=(8-i);
		}
	}
	return ans;
}

bool ok(Node *n) 
{
	if (n->b[2][2]!='x')
	{
		return false;
	}
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			if (i==2&&j==2)
			{
				continue;
			}
			if (n->b[i][j]-'0'!=3*i+j+1)
			{
				return false;
			}
		}
	}
	return true;
}

void printsol(Node *front)
{
	if (front->prev)
	{
		printsol(front->prev);
	}
	if (front->prev)
	{
		putchar(front->move);
	}
}

struct cmp//优先队列的比较器
{
	bool operator()(Node *p,Node *q)
	{
		int m=p->g+p->h,n=q->g+q->h;
		if (m!=n) return m>n;		
		return p->g<q->g;//如果f值相同,g值小的优先级低(因为不确定性大)
	}
};


void astar()
{
	memset(v, 0, sizeof(v));
	priority_queue<Node*,vector<Node *>,cmp> q;  // 小根堆
	Node *first = new Node;
	first->prev = 0;
	first->g = 0;
	for (int i = 0; i<3; i++)
	{
		for (int j = 0; j<3; j++)
		{
			first->b[i][j] = a[3*i+j];
			if (a[3*i+j] == 'x')
			{
				first->x = i;
				first->y = j;
			}
		}
	}
	first->h = h(first); // 计算起点的代价函数
	q.push(first);
	v[cantor(first->b)] = true; 
	Node *front;
	while(!q.empty())
	{
		front = q.top(); // 优先开拓更接近真实答案的那个
		if (ok(front)) // 根据【3】第四个问题的论述, 是不需要剪枝的.
		{
			break;
		}
		q.pop(); // 根据【3】的第五个问题的论述, 我们没必要将已经出堆的节点重新入堆
		for (int i = 0,nx,ny; i<4; i++) 
		{
			nx = front->x+dir[i][0];
			ny = front->y+dir[i][1];
			if (nx<0||nx>2||ny<0||ny>2) 
			{
				continue;
			}
			swap(front->b[front->x][front->y], front->b[nx][ny]);
			int tc = cantor(front->b);
			if (v[tc])
			{
				swap(front->b[front->x][front->y], front->b[nx][ny]);
				continue;
			}
			Node *n = new Node;
			n->x = nx, n->y = ny;
			switch(i)
			{
			case 0:
				n->move = 'u';
				break;
			case 1:
				n->move = 'd';
				break;
			case 2:
				n->move = 'l';
				break;
			case 3:
				n->move = 'r';
				break;
			default:
				break;
			}
			memcpy(n->b, front->b, sizeof(n->b));
			n->prev = front;
			swap(front->b[front->x][front->y], front->b[nx][ny]); 
			n->g = front->g+1;
			n->h = h(n); // 计算新开辟的节点的真实代价函数和启发式函数
			q.push(n);
			v[tc] = true;
		}
	}
	if (q.empty())
	{
		puts("unsolvable");
	}
	else
	{
		printsol(front);
		puts("");
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%c", a))
	{
		if (read())
		{
			puts("unsolvable");
			continue;
		}
		astar();
		getchar();
	}
	return 0;
}

ac情况（性能爆表~飙到了 32ms~ hdu 1043 上还是被MLE卡掉了）而且内存使用的很少（是dbfs的1/5）, 说明A* 算法搜索的节点更少了~

Status	Accepted
Time	32ms
Memory	912kB
Length	3668
Lang	C++
Submitted	2019-09-18 14:31:58
Shared
RemoteRunId	20871101

参考

【1】https://yfsyfs.github.io/2019/09/05/%E5%88%86%E6%94%AF%E9%99%90%E7%95%8C-bfs-%E6%90%9C%E7%B4%A2-%E7%9A%84%E4%B8%80%E8%88%AC%E6%80%A7%E8%AE%BA%E8%BF%B0/

【2】https://yfsyfs.github.io/2019/09/13/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80%E6%B1%82%E5%85%A8%E6%8E%92%E5%88%97/

【3】https://yfsyfs.github.io/2019/09/05/%E5%88%86%E6%94%AF%E9%99%90%E7%95%8C-bfs-%E6%90%9C%E7%B4%A2-%E7%9A%84%E4%B8%80%E8%88%AC%E6%80%A7%E8%AE%BA%E8%BF%B0/