CF1063B

因为本人的粗心wa了一早上,写篇博客记录一下

题目CF1063BCF1063Bhttps://www.luogu.com.cn/problem/CF1063B

 

题意描述

你正在玩一款电脑游戏。在其中一关,你位于一个 nn 行 mm 列的迷宫。每个格子要么是可以通过的空地,要么是障碍。迷宫的起点位于第 rr 行第 cc 列。你每一步可以向上、下、左、右中的一个方向移动一格,前提是那一格不是障碍。你无法越出迷宫的边界。

不幸的是,你的键盘快坏了,所以你只能向左移动不超过 xx 格,并且向右移动不超过 yy 格。因为上下键情况良好,所以对向上和向下的移动次数没有限制。

现在你想知道在满足上述条件的情况下,从起点出发,有多少格子可以到达(包括起点)?

输入输出格式

输入格式:

第一行包含两个数 n, mn,m (1 <= n, m, <= 2000)(1<=n,m,<=2000) ,表示迷宫的行数和列数。

第二行包含两个数 r,cr,c (1 <= r <= n, 1 <= c <= m)(1<=r<=n,1<=c<=m) ,表示起点位于第 rr 行第 cc 列。

第三行包含两个数 x,yx,y (1 <= x,y <= 10^9)(1<=x,y<=109) ,表示最多向左或向右移动的次数。

接下来 nn 行描述这个迷宫,每行为一个长为 mm 的由 '.' 和 '*' 组成的字符串。 '.' 表示空地, '*' 表示障碍。 输入保证起点不是障碍。

输出格式:

输出一个整数,表示从起点出发可以到达的格子数,包括起点本身。

刚开始写的时候是先写的dfs(深度搜索),显然wa了

本题要求:搜索所有能到达的点的个数,还有一个附加条件:向左向右的次数是有限的!

First example:  s(3,2) x=1,y=2

+表示可以访问的点,我们可以看到(1,3)这个点并不是  2+2=4

这是因为先走到了点(1,1)此时的  r  为0,一直走到r=2时,就为(1,3)

+++..
+***.
+++**
*+++.

所以本题不是简单的  坐标比S.y-maxr大,比S.y+maxl小就行了

于是用dfs出现了一个问题,刚才访问过的点显然并不是最短路径,一个点必然是有多条路径的,dfs的问题是他无法计算一个点的最小路径,如果不加visit数组让一个点重复计数,必然会达到死循环,dfs做本题不太方便

本题的坑爹点在于:一个点有许多条路径,于是就导致了一个点从不同路径进入,他的左边最小步数和右边最小步数是不同的--》于是用到了广度优先搜索(bfs)

/*以下是本题bfs的基本模板*/
while (!Q.empty())
	{
		v = Q.front();
		Q.pop();			//弹出一个
		
		for (int i = 0;i < 4;i++)
		{
			p = v;
			p.x += a1[i];
			p.y += a2[i];
			if (i == 1) p.l += 1;
			if (i == 2) p.r += 1;
				if (check(p.x,p.y,p.l,p.r))            //这个点可不可取
				{
					visit[p.x][p.y] = 1;
					number++;
					cnt[p.x][p.y].l = p.l;
					cnt[p.x][p.y].r = p.r;
					Q.push(p);
				}
         }
     }

可以发现,如果bfs只按照这个模板进去,就会发现上述问题,没有选择到一个最短路径,会wa几个点,bfs虽然可以解决一部分最短路径的问题,但终究是有限的,需要增加一个新的选择语句if,

思路:如果这个点已经访问过了,但是此时的步数比原本的步数还小,就让他替换原来的值,成为新的擂主,然后同时入队(因为这个点已经最小了,那么同时他周围的点也可能会取到最小值)

else if (p.x >= 0 && p.y >= 0 && p.x < n && p.y < m && visit[p.x][p.y])
			{
				if (p.l < cnt[p.x][p.y].l && (p.r < cnt[p.x][p.y].r))
				{//两个都是最小值
					cnt[p.x][p.y].l = p.l;
					cnt[p.x][p.y].r = p.r;
					Q.push(p);
				}
				if ((p.l < cnt[p.x][p.y].l && p.r > cnt[p.x][p.y].r) || p.r < cnt[p.x]
[p.y].r && p.l > cnt[p.x][p.y].l)//其中一个小于最小值
					Q.push(p);
			}

源代码如下

#include <iostream>
#include <queue>
using namespace std;
int n, m;
int r, c;
int maxl, maxr;
char s[2005][2005] = { 0 };
int visit[2005][2005];
int a1[] = { -1,0,0,1 };				//上下移动
int a2[] = { 0,-1,1,0 };				//左右移动
struct node
{
	int x, y;
	long l;
	long r;
};
struct point
{
	long l;
	long r;
};
point cnt[2005][2005];
queue<node> Q;
bool check(int i, int j, int l, int r)//判断这一步是否可走 
{    //******注意此时由于是长方形,所以j<m,要注意不要写成j<n!!!!
	return (i >= 0 && i < n&& j >= 0 && j < m&& l <= maxl && r <= maxr && !visit[i][j] && s[i][j] != '*');
	//判断是否走出地图,左右移动步数是否满足要求以及是否走过这个点并且这个点可以走
}
int bfs(int x, int y)
{
	int number = 0;
	node p;
	node v = { x,y,0,0 };
	cnt[x][y].l = cnt[x][y].r = 0;
	if (Q.empty())
		Q.push(v);
	visit[r][c] = 1;
	number++;
	while (!Q.empty())
	{
		v = Q.front();
		Q.pop();			//弹出一个

		for (int i = 0;i < 4;i++)
		{
			p = v;
			p.x += a1[i];
			p.y += a2[i];
			if (i == 1) p.l += 1;
			if (i == 2) p.r += 1;
			if (check(p.x, p.y, p.l, p.r))
			{
				visit[p.x][p.y] = 1;
				number++;
				cnt[p.x][p.y].l = p.l;
				cnt[p.x][p.y].r = p.r;
				Q.push(p);
			}
			else if (p.x >= 0 && p.y >= 0 && p.x < n && p.y < m && visit[p.x][p.y])
			{
				if (p.l < cnt[p.x][p.y].l && (p.r < cnt[p.x][p.y].r))
				{
					cnt[p.x][p.y].l = p.l;
					cnt[p.x][p.y].r = p.r;
					Q.push(p);
				}
				if ((p.l < cnt[p.x][p.y].l && p.r > cnt[p.x][p.y].r))
                    Q.push(p);
                if(p.r < cnt[p.x][p.y].r && p.l > cnt[p.x][p.y].l)
                //其中一个小于最小值
					Q.push(p);
			}


		}

	}
	return number;
}
int main()
{
	memset(cnt, 0x3f, sizeof(cnt));
	int number = 0;
	cin >> n >> m;				//迷宫长度
	cin >> r >> c;				//起点
	r--;c--;
	cin >> maxl >> maxr;				//向左向右最大移动次数
	for (int i = 0;i < n;i++)
		for (int j = 0;j < m;j++)
		{
			cin >> s[i][j];
		}
	number = bfs(r, c);
	cout << number;
	return 0;
}

上一篇:leetcode刷题笔记——733图像渲染


下一篇:CF1574D.The Strongest Build (bfs)