题目

题目链接

题解

暴力DFS。

没想到直接暴力DFS就行。

暴力选边，对于每条边可以选择选，也可以选择不选；

dfs过程可以有两种方式：
其一：每次选此边时都先判断一下，选了此边会不会成环，若成环，则不能选此边，若不会构成，则可以选此边。
其二：每次选边不进行判断，而是深搜到底且选取边的个数满足要求时，对全部被选的边进行判断，若不构成环则答案加一。
两种方式均可，第一种耗时少；两种方式分别对应代码1，代码2。

判断是否为环利用的是并查集的思想（有点类似于最小生成树的克鲁斯卡尔算法）：
第一种方式中判断是否构成环，判断搜索到的边的两个端点是否具有相同的根，若具有则不可以选此边，若不具有相同根，则进行类似于并查集中join函数的操作，注意在dfs完后回溯fa数组的值，这点尤其关键，而且不可以在find函数中进行路径压缩，会导致得不到正确答案（具体原因不知道，因为模拟这个回溯过程太难了，如果有大佬有简单易懂的方式去理解，望不吝赐教）
第二种方式中，我们只需要在遍历全部被选中的边，判断是否存在同根的情况，若不存在则调用join函数，若存在则直接返回就行了，这种选法肯定是不对的；这里的join可以压缩。

两个代码的存储方式是一模一样的，理解了其中一个另一个很好理解。

代码1

#include<bits/stdc++.h>
#define a first
#define b second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;

int n, m, ans, flag[N], fa[N], pnum;
vector<PII> edge;
char ch;

int find(int x) { 
	int r = x;
	while(r!=fa[r]) r = fa[r];
	return r;
}

void dfs(int id, int sum) { // id表示边在edge中的索引， sum表示已选边的个数
	
	if(id == edge.size()) {
		if(sum == pnum - 1) ans ++; // 构成一棵树了 
		return ;
	}
	
	// 选 
	int x = edge[id].a, y = edge[id].b;
	int rx = find(x), ry = find(y);
	if(rx != ry) { // 添加此边并不会构成环 
		int rrx = fa[rx];
		fa[rx] = ry; // 其实就是并查集中的join函数 
		dfs(id+1, sum+1);
		fa[rx] = rrx; // 对join函数的操作进行回溯 
	} 
	
	// 不选 
	dfs(id+1, sum);
}

int main()
{
	cin>>n>>m;
	for(int i = 0;i < n;i ++) 
	for(int j = 0;j < m;j ++) {
		cin>>ch;
		int cur = i*m+j; // 点的编号 
		fa[cur] = cur; // 初始化fa数组 
		if(ch == 'E') {
			pnum ++; // number of point E 点E的个数 
			flag[cur] = 1; // flag[i]=1表明编号为i的位置为E 
			int left = (i-1)*m+j, up = i*m+j-1; // left：(i-1, j)的编号  up：(i,j-1)的编号 
			if(i > 0 && flag[left]) edge.push_back(PII(left, cur)); // 未发生越界，并且(i-1, j)位置上为E，则将边(i-1,j)--(i,j)添加进去 
			if(j > 0 && flag[up]) edge.push_back(PII(up, cur)); // 未发生越界，并且(i, j-1)位置上为E，则将边(i,j-1)--(i,j)添加进去 
		} 
	}	
	
	dfs(0, 0); 

	cout << ans << endl;
	return 0;
}

代码2

#include<bits/stdc++.h>
#define a first
#define b second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;

int n, m, ans, flag[N], vis[N<<1], fa[N], pnum, st, here;
vector<PII> edge;
char ch;
int best[N];

int find(int x) {
	int r = x;
	while(r!=fa[r]) r = fa[r];
	
	int tmp;
	while(x!=r) {
		tmp = fa[x];
		fa[x] = r;
		x = tmp;
	}
	
	return r;
}

void join(int x, int y) {
	int rx = find(x), ry = find(y);
	if(rx != ry) fa[rx] = ry;
}

void dfs(int id, int sum) {
	
	if(id == edge.size()) {
		if(sum == pnum - 1) {
			for(int i = 0;i < n*m;i ++) fa[i] = i; // 初始化fa 
			for(int i = 0;i < edge.size();i ++) {
				if(vis[i]) { // 此边被选 
					int rx = find(edge[i].a), ry = find(edge[i].b);
					if(rx==ry) return ; // 同根直接返回 
					join(edge[i].a, edge[i].b); 
				}
			}
			ans ++;
		}
		return ;
	}
	
	dfs(id+1, sum); // 不选 
	
	vis[id] = 1;
	dfs(id+1, sum+1); // 选 
	vis[id] = 0;
}

int main()
{
	cin>>n>>m;
	for(int i = 0;i < n;i ++) 
	for(int j = 0;j < m;j ++) {
		cin>>ch;
		int cur = i*m+j;
		fa[cur] = cur;
		if(ch == 'E') {
			pnum ++;
			flag[cur] = 1;
			int left = (i-1)*m+j, up = i*m+j-1;
			if(i > 0 && flag[left]) edge.push_back(PII(left, cur));
			if(j > 0 && flag[up]) edge.push_back(PII(up, cur));
		} 
	}	
	
	dfs(0, 0);

	cout << ans << endl;
	return 0;
}