Labyrinth CodeForces - 1064D

Posted by PowderHan on January 9, 2019 已经被偷看过次啦QAQ

http://www.170mv.com/kw/other.web.nf01.sycdn.kuwo.cn/resource/n3/12/35/426206898.mp3




Labyrinth

$CodeForces$ - $1064D$

原题传送门

题目大意

给定一个n*m的地图,从某个位置开始,每次可以向上下左右四个方向之一走一步
但限制了向左走和向右走的次数。地图中也有障碍物,求有多少个地方是可以到达的

思路

考虑到一共只有l+r步可以左右走的次数,那对于每一次扩展,必然是要么减少一次左右走的机会,要么上下走不影响剩余机会数
考虑无向图的遍历,则其中的边权可能为0或者1,对于这种0/1边权的无向图,为了保证bfs队列的单调性,我们使用双端搜索来完成。
即可使用deque双端队列,对于边权为0也就是上下走的扩展,我们将它插入队头。而对于边权为1也就是左右走的扩展,我们将它插入队尾。
这样整个队列中的”step“是单调递增的。这样就可以保证第一次到达某个点的时候一定是其最短的路径。

代码

  
#include <iostream>
	
#include <cstring>
	
#include <cstdio>

#include <deque>
	
using namespace std;

const int MAXN = 2005;
struct point
{
	int x, y;
	int l, r;
};
bool vis[MAXN][MAXN];
int g[MAXN][MAXN];
int n, m;
point s;

void init()
{
	cin >> n >> m;
	cin >> s.x >> s.y;
	cin >> s.l >> s.r;
}

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

inline bool valid(const int &x, const int &y)
{
	return x <= n && y <= m && x >= 1 && y >= 1;
}

void bfs()
{
	deque<point> q;
	vis[s.x][s.y] = 1;
	q.push_back(s);
	while (!q.empty())
	{
		point u = q.front();
		q.pop_front();
		int &x = u.x;
		int &y = u.y;
		int &l = u.l;
		int &r = u.r;
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (!valid(nx, ny) || vis[nx][ny] || !g[nx][ny])
				continue;
			if (i == 0 && l)
			{
				q.push_back((point){nx, ny, l - 1, r});
				vis[nx][ny] = 1;
			}
			else if (i == 1 && r)
			{
				q.push_back((point){nx, ny, l, r - 1});
				vis[nx][ny] = 1;
			}
			else if (i == 2 || i == 3)
			{
				q.push_front((point){nx, ny, l, r});
				vis[nx][ny] = 1;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (vis[i][j])
				ans++;
	cout << ans << endl;
}

void work()
{
	char ch;
	getchar();
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			ch = getchar();
			if (ch == '.')
				g[i][j] = 1;
			else
				g[i][j] = 0;
		}
		getchar();
	}
	bfs();
}

int main()
{
	init();
	work();
	return 0;
}

code paste

code paste

注意

对于 $vis$ 的使用,一开始是直接放在 $while$ 循环的 $continue$ 后面,这样导致最后答案会变多,
因为可能扩展出的 $nx$ 和 $ny$ 前面的条件都满足,但其实他是在 $l0||r0$ 对应的不能走的情况下扩展的。
实际上这个点不能入队也就是不能探索到,但还是标记了它。
后来改成了对于当前队头的 $u$,将 $vis[u.x][u.y]$ 更新为 $1$ .但这样导致了 $TLE$
因为只有当一个点到达队头时才会被标记已访问过,那在其入队后但是未到队头时,有可能会重复访问并且重复入队。
这样会导致队列中有很多重复点,所以会导致 $TLE$ 。


The total number of English words:954
The total number of Chinese words:2409
欢迎点击下方的知乎图标关注我的知乎QAQ
毕生梦想-成为知乎大V
蟹蟹~