[ABC219E] Moat 题解

思路解析

一眼看到输入数据只有 \(4\) 行 \(4\) 列，直接想到状压枚举。可以直接枚举所有护城河所包含起来的格子，判断是否连通以及判断是否包含住了所有村庄。判断连通我选择用洪水填充，随便选一个包含着的格子，若可以通过当前格移动到所有被包含格就说明连通。以及还要判断被包围格子是否形成了一个环，例如：

其中蓝线表示护城河，绿色阴影表示护城河包围的格子。可见图中有两条护城河，不符合题意。为排除掉这种情况，我们判断每一个没有被选择的格子，判断它是否被护城河完全包围，也就是判断能否走到地图外即可。

时间复杂度：首先一次暴力枚举，然后对于每种情况需要判断是否为可行方案，洪水填充最多遍历 \(16\) 个格子，复杂度为 \(2^{16} \times 16\)。

code

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define fir first
#define sec second
int v[8][8], flag[8][8], f[8][8], ans = 0;
bool vis[8][8];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
void flood(int x, int y) {
	queue< PII > q;
	q.push({x, y});
	while(!q.empty()) {
		int xx = q.front().fir, yy = q.front().sec;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = xx + dx[i], ny = yy + dy[i];
			if(flag[nx][ny] && !f[nx][ny]) {
				f[nx][ny] = true;
				q.push({nx, ny});
			}
		}
	}
}
bool flood_loop(int x, int y) {
	queue< PII > q;
	q.push({x, y});
	memset(vis, false, sizeof(vis));
	vis[x][y] = true;
	while(!q.empty()) {
		int xx = q.front().fir, yy = q.front().sec;
		q.pop();
		for(int i = 0; i < 4; i++) {
			int nx = xx + dx[i], ny = yy + dy[i];
			if(!flag[nx][ny] && !vis[nx][ny]) {
				if(nx >= 1 && nx <= 4 && ny >= 1 && ny <= 4) {
					vis[nx][ny] = true;
					q.push({nx, ny});
				}
				else return true;
			}
		}
	}
	return false;
}
int check() {
	int x = 0, y = 0, cnt = 0;
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(flag[i][j]) cnt++, x = i, y = j;
		}
	}
	memset(f, 0, sizeof(f));
	f[x][y] = 1;
	flood(x, y);	//洪水填充判断连通
	int sum = 0;
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(f[i][j]) sum++;
		}
	}
	if(sum != cnt) return 0;	//不连通
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(v[i][j] && !f[i][j]) return 0;	//若有村庄没被包含
		}
	}
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			if(!flag[i][j] && !flood_loop(i, j)) return 0;	//被护城河完全包围
		}
	}
	return 1;
}
void dfs(int x, int y) {	//暴力枚举
	if(y > 4) y = 1, x++;
	if(x > 4) {
		ans += check();
		return;
	}
	flag[x][y] = 1;
	dfs(x, y + 1);
	flag[x][y] = 0;
	dfs(x, y + 1);
}
int main() {
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= 4; j++) {
			cin >> v[i][j];
		}
	}
	dfs(1, 1);
	cout << ans;
	return 0;
}