[杭电多校1 | HDUOJ]7139.Dragon Slayer（dfs + 暴力枚举）

题目链接：Problem - 7139 (hdu.edu.cn)

题目 / Problem

给定一个N x M的地图和K堵墙（N, M, K <= 15），注意这里的墙在方格的边缘而非方格内，需要进行移动判定。

给一个起点(sx, sy)和终点(fx, fy)。

问最少移除几道墙可以从起点走到终点。

思路 / Thought

做题往往从数据范围小的变量入手，比如本题的K。

因为K很小，2的15次方也才不过3e4左右，所以我们完全可以枚举出墙的所有开合情况，用一个数字u的各个二进制位表示某堵墙是否被推倒，再验证这种情况的起点和终点是否连通，若连通就更新答案。

复杂度为O(N * M * 2 ^ K)，最大是1e7左右，很健康的复杂度。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 20;
int sx, sy, fx, fy, N, M, K;
bitset<maxn> vis[maxn], col[maxn], row[maxn];
struct Wall
{
	int x1, y1, x2, y2;
}w[maxn];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

int lowbit(int x){return x & -x;}

int getcnt(int x)
{
	int res = 0;
	while(x)x -= lowbit(x), res ++;
	return K - res;
}

bool judge(int x,int y,int dir)//判断某点往dir方向是否可行 
{
	if(dir == 0)return !(col[x][y + 1] && col[x + 1][y + 1]);
	else if(dir == 1)return !(col[x][y] && col[x + 1][y]);
	else if(dir == 2)return !(row[x + 1][y] && row[x + 1][y + 1]);
	else if(dir == 3)return !(row[x][y] && row[x][y + 1]);
	return 0;
}

bool dfs(int x, int y)
{
	vis[x][y] = 1;
	if(x == fx && y == fy)return 1;
	for(int i = 0;i < 4; ++ i)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if(nx < 0 || nx >= N || ny < 0 || ny >= M || vis[nx][ny])continue;
		if(judge(x, y, i) && dfs(nx, ny))return 1;
	}
	return 0;
}

bool check(int u)
{
	for(int i = 0;i <= N; ++ i)
	{
		vis[i].reset();
		col[i].reset();
		row[i].reset();
	}
	for(int i = 0;i < K; ++ i)
	{
		if(u & 1)
		{
			int x1 = w[i].x1, y1 = w[i].y1, x2 = w[i].x2, y2 = w[i].y2;
			
			if(x1 == x2)
			{
				if(y1 >= y2)swap(y1, y2);
				for(int i = y1;i <= y2; ++ i)row[x1][i] = 1;
			}
			else if(y1 == y2)
			{
				if(x1 >= x2)swap(x1, x2);
				for(int i = x1;i <= x2; ++ i)col[i][y1] = 1;
			}
		}
		u >>= 1;
	}
	return dfs(sx, sy);
}

void solve()
{
	cin >> N >> M >> K;
	cin >> sx >> sy >> fx >> fy;
	for(int i = 0;i < K; ++ i)cin >> w[i].x1 >> w[i].y1 >> w[i].x2 >> w[i].y2;
	int ans = K;
	for(int u = 0;u < (1 << K); ++ u)//u表示墙的开合状态 
		if(check(u))ans = min(ans, getcnt(u));
	cout << ans << '\n';
}

signed main()
{
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}