Solitaire HDU - 1401 双向BFS

题解

题目大意，一个棋盘上有四个旗子，给你当前状态和目标状态的旗子，每次可以移动一个旗子也可以跳过另一个旗子，问8次内是否能到达目标状态。

只要常数压的好普通BFS也能过，这里使用双向BFS求解，从初始状态和目标状态同时搜索。
节点记录四个点的位置和操作次数，排序后每个点占用两个10进制位，位压缩为8位10进制作为hash值用unordered_set判重。
每个节点至多操作4次，当当前分支的hash状态在另一个分支的set中出现则说明相汇直接return 1即可。

AC代码

#include <stdio.h>
#include <unordered_set>
#include <bits/stdc++.h>
#define fst first
#define sed second
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };

struct node
{
	int p[4], k; //四个点 次数
	bool find(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;
	}
};
int DBFS()
{
	int a;
	node t;
	t.k = 0;
	queue<node> q[2];
	unordered_set<int> st[2]; //使用set标记访问
	for (int k = 0; k < 2; ++k)
	{
		for (int i = 0; i < 4; ++i)
		{
			t.p[i] = 0;
			for (int j = 0; j < 2; ++j)
			{
				if (scanf("%d", &a) == EOF)
					exit(0);
				t.p[i] = t.p[i] * 10 + a;
			}
		}
		q[k].emplace(t);
		st[k].insert(t.hash());
	}
	while (!q[0].empty() || !q[1].empty())
		for (int i = 0; i < 2; ++i) //分支
			if (!q[i].empty())
			{
				node f = q[i].front(); q[i].pop();
				/*
				if (f.hash() == 11121381)
					cout << endl;
				*/
				if (st[!i].find(f.hash()) != st[!i].end()) //相汇
					return 1;
				f.k++; //直接+1方便构造
				for (int j = 0; j < 4; ++j) //4个点
				{
					int x = f.p[j] / 10, y = f.p[j] % 10; //得到点位置
					for (int k = 0; k < 4; ++k) //方向
					{
						int xx = x + dir[k][0], yy = y + dir[k][1];
						if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && f.find(xx * 10 + yy)) //未出界且移动位置有点
							xx += dir[k][0], yy += dir[k][1]; //再次移动
						if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8 && f.k <= 4 && //未出界且已经操作次数小于4
							!f.find(xx * 10 + yy)) //最终的移动结果无点
						{
							f.p[j] = xx * 10 + yy; //更新位置
							if (st[i].find(f.hash()) == st[i].end()) //未出现的状态
								q[i].emplace(f), st[i].insert(f.hash()); //入队标记访问
						}
					}
					f.p[j] = x * 10 + y; //还原位置
				}
			}
	return 0;
}
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	while (true)
		printf("%s\n", DBFS() ? "YES" : "NO");

	return 0;
}