ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年7月25日 228点热度 1人点赞 0条评论

题目链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ dfs hduoj 图论
最后更新:2022年7月25日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号