2022杭电多校第一场B题Dragon slayer-Toy模板网

这篇具有很好参考价值的文章主要介绍了2022杭电多校第一场B题Dragon slayer。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

数据范围为15，直接枚举所有墙的方案，然后看是否能搜索到终点，如果可以就更新ans

需要注意的是如何处理：起点终点坐标+0.5造成的下标为小数，这里把所有坐标都乘2来避免double类型的出现

代码如下：文章来源地址https://www.toymoban.com/news/detail-578608.html

#include<iostream>
#include<cstring>
using namespace std;

const int N = 15 * 2 + 5;

int map[N][N];
bool st[N][N];

int dx[4] = {0, -1, 1, 0}, dy[4] = {1, 0, 0, -1};
int xs, ys, xt, yt, k, ans, n, m;

struct wall
{
	int x1, y1, x2, y2;
}w[N];

void dfs(int x, int y, int cnt)
{
	st[x][y] = true;
	if (x == xt && y == yt)
	{
		ans = cnt;
		return;
	} 

	for (int i = 0; i < 4; i++)
	{
		int xc = dx[i] + x, yc = dy[i] + y;
		if (xc > 0 && yc > 0 && xc < (n * 2) && yc < (m * 2) && !st[xc][yc] && !map[xc][yc])
			dfs(xc, yc, cnt);
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	
	while(t--)
	{
		ans = 0x3f3f3f3f;
		scanf("%d%d%d", &n, &m, &k);
		
		scanf("%d%d%d%d", &xs, &ys, &xt, &yt);
		
		xs *= 2, ys *= 2, xt *= 2, yt *= 2;
		xs += 1, ys += 1, xt += 1, yt += 1;
		
		for (int i = 0; i < k; i++)
		{
			int x1, x2, y1, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			w[i] = {x1, y1, x2, y2};
		}
		
		for (int state = 0; state < 1 << k; state++)
		{
			memset(map, 0, sizeof map);
			memset(st, 0, sizeof st);
			int cnt = 0;
			
			for (int i = 0; i < k; i++)
			{
				if (state >> i & 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 j = y1 * 2; j <= y2 * 2; j++)
							map[x1 * 2][j] = 1;
					}
					else
					{
						if (x1 > x2) swap(x1, x2);
						
						for (int j = x1 * 2; j <= x2 * 2; j++)
							map[j][y1 * 2] = 1;
					}
				}
				else cnt++;
			}
			
			if (ans < cnt) continue;
			dfs(xs, ys, cnt);
		}
		
		printf("%d\n", ans);
	}
	
	return 0;
}

到了这里，关于2022杭电多校第一场B题Dragon slayer的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！