洛谷：P1444 [USACO1.3]虫洞 wormhole（找环 + 枚举暴搜）

洛谷：P1444 [USACO1.3]虫洞 wormhole（找环 + 枚举暴搜） 虫虫虫洞

当存在环的时候，就会出现无限循环，也就相当于 dfs 时走回了曾经走过的地方

数据范围很小，我们可以枚举两两配对，然后搜索每一个点出发能产生的结果，判断是否会无限循环，若否就统计方案数

同时这里可以用一个排序减少工作量

C o d e : Code: Code:

#include
#include
#include
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
//#define x first
//#define y second
//#pragma GCC optimize(2)
//[博客地址](https://blog.csdn.net/weixin_51797626?t=1) 
using namespace std;

typedef long long ll;
typedef pair PII;
typedef pair  PI;

const int N = 15, M = 200010, MM = N;
int INF = 0x3f3f3f3f, mod = 100003;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
struct node
{
	int a, b;
	bool operator <(const node& nn)const {
		if (b != nn.b)return b < nn.b;
		return a < nn.a;
	}
}nod[N];
int ans, mat[N];

//add记录经过多少点，x为当前点编号，begin为初始进入的点的状态，t代表该点是准备进虫洞还是从虫洞出来
bool pan(int add, int x, PII begin, int t) {
	if (add != 1 && begin == PII(x, t))return true;
	//当之后再次跑到此点且状态一致时，成环

	if (t == 0) { //从虫洞出来
		if (nod[x].b != nod[x + 1].b)return false;//因为排过序，下一个点纵坐标不一致不可能成环
		return pan(add + 1, x + 1, begin, 1);
		//一致肯定保证横坐标距离最近，走过去，更新t
	}
	else return pan(add + 1, mat[x], begin, 0);
	//准备进虫洞，传到匹配点的位置
}

bool check() {
	for (int i = 1; i <= n; i++)//每一个点都去判断有没有成环的情况
		if (pan(1, i, { i,1 }, 1))return true;
	return false;
}

void dfs(int x) {
	if (x == n + 1) { if (check())ans++; return; }//枚举匹配完了就判断该情况
	if (mat[x] == 0) { 
		for (int i = x + 1; i <= n; i++)
			if (mat[i] == 0) {
				mat[i] = x, mat[x] = i;//记录彼此
				dfs(x + 1);
				mat[i] = mat[x] = 0;//恢复现场
			}
	}
	if (mat[x] != 0)dfs(x + 1);//匹配过了搜下一个
	return;
}

int main() {
	cinios;

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		nod[i] = { a,b };
	}
	sort(nod + 1, nod + 1 + n);//对于记录的点根据先纵坐标递增、再横坐标递增排序

	dfs(1);

	cout << ans;

	return 0;
}