HDU - 1401 Solitaire（两种方法）

题目链接： Solitaire

---

大致题意:

在8*8棋盘有四颗棋子，输入开始状态和目标状态的棋子坐标，每次可以移动一个棋子也可以跳过另一个棋子，问能否在8步内走到目标状态

---

解题思路:

第一种做法：
正常bfs，开一个八维数组
注意：数组大小只能为8，不然会超内存

第二种做法：
双向广搜，8个坐标值位压缩成为10进制作为hash值，并用unordered_set判重，当hash值出现在另一个分支即相遇
剪枝：每个棋子最多只能走4步，因为如果多于4步，那么他们步数之和就会大于8

---

AC代码:

//第一种方法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
bool vis[8][8][8][8][8][8][8][8];
int g[10][10];
int fx[][2] = { 1,0,-1,0,0,1,0,-1 };
struct node {
	int x[4], y[4];
	int step;
}s, e;
bool check(node a) {   //判断是否到终点
	for (int i = 0; i < 4; ++i) 
		if (!g[a.x[i]][a.y[i]])return 0;
	return 1;
}
bool judge(node a) {  //考虑边界和是否走过
	for (int i = 0; i < 4; ++i)
		if (a.x[i] < 0 || a.x[i] >= 8 || a.y[i] < 0 || a.y[i] >= 8)return 1;
	if (vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]])return 1;
	return 0;
}
bool empty(node a, int k) {  //判断下一位置是否为空
	for (int i = 0; i < 4; ++i)
		if (i != k && a.x[i] == a.x[k] && a.y[i] == a.y[k])return 0;
	return 1;
}
bool bfs() {
	memset(vis, 0, sizeof vis);
	queue<node>q;
	node a, b;
	a.step = 0;
	for (int i = 0; i < 4; ++i) {
		a.x[i] = s.x[i];
		a.y[i] = s.y[i];
	}
	q.push(a);
	vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]] = 1;
	while (!q.empty()) {
		a = q.front(); q.pop();
		if (a.step >= 8)return 0;
		if (check(a))return 1;
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j) {
				b = a;
				b.x[i] += fx[j][0]; b.y[i] += fx[j][1];
				b.step++;
				if (judge(b))continue;
				if (empty(b, i)) {  //下一格为空
					if (check(b))return 1;
					vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;
					q.push(b);
				}
				else {  //不为空，要再走一步
					b.x[i] += fx[j][0]; b.y[i] += fx[j][1];
					if (judge(b) || !empty(b, i))continue;
					if (check(b))return 1;
					vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;
					q.push(b);
				}
			}
	}
	return 0;
}
int main() {
	while (cin >> s.x[0] >> s.y[0]) {
		s.x[0]--;s.y[0]--;   //必须减1，不然没存会超
		for (int i = 1; i < 4; ++i) {
			cin >> s.x[i] >> s.y[i];
			s.x[i]--;s.y[i]--;
		}
		memset(g, 0, sizeof g);
		for (int i = 0; i < 4; ++i) {
			cin >> e.x[i] >> e.y[i];
			e.x[i]--;e.y[i]--;
			g[e.x[i]][e.y[i]] = 1;
		}
		bool flag = bfs();
		if (flag)cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

//第二种方法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
#include<queue>
using namespace std;
int fx[][2] = { 0,1,0,-1,1,0,-1,0 };
struct node {
	int p[4], step;
	bool check(int v) {
		for (int i : p)
			if (i == v)return 1;
		return 0;
	}
	int hash() {
		int a[4];
		memcpy(a, p, sizeof a);
		sort(a, a + 4);
		int res = 0;
		for (int i : a)res = res * 100 + i;
		return res;
	}
};
unordered_set<int>st[2];
queue<node>q[2];
void clear() {
	for (int i = 0; i < 2; ++i) {
		queue<node>tmp;
		swap(q[i], tmp);
		st[i].clear();
	}
}
bool flag(int i, int hash) {  //队列下标和待查hash
	if (st[i].find(hash) != st[i].end())return 1; //相遇
	return 0;
}
bool bfs() {
	while (!q[0].empty() || !q[1].empty()) {
		for (int i = 0; i < 2; ++i) { //两个队列
			if (!q[i].empty()) {
				node tmp = q[i].front(); q[i].pop();
				tmp.step++;
				for (int j = 0; j < 4; ++j) { //四个点
					int x = tmp.p[j] / 10, y = tmp.p[j] % 10;
					for (int k = 0; k < 4; ++k) { //四个方向
						int dx = x + fx[k][0], dy = y + fx[k][1];
						if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && tmp.check(dx * 10 + dy))
							dx += fx[k][0], dy += fx[k][1];
						if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && !tmp.check(dx * 10 + dy) && tmp.step <= 4) {
							tmp.p[j] = dx * 10 + dy;
							if (st[i].find(tmp.hash()) == st[i].end()) {
								if (flag(!i, tmp.hash()))return 1;
								q[i].push(tmp); st[i].insert(tmp.hash());
							}
						}
					}
					tmp.p[j] = x * 10 + y; //回溯
				}
			}
		}
	}
	return 0;
}
int main() {
	while (true) {
		clear();
		node tmp; tmp.step = 0;
		for (int k = 0; k < 2; ++k) {
			for (int i = 0; i < 4; ++i) {
				tmp.p[i] = 0;
				for (int j = 0; j < 2; ++j) {
					int x; if (scanf("%d", &x) == EOF)exit(0);
					tmp.p[i] = tmp.p[i] * 10 + x;
				}
			}
			q[k].push(tmp);
			st[k].insert(tmp.hash());
		}
		if (flag(0, q[1].front().hash()) || bfs())cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

END