Labyrinth

wjh15101051's space

卧薪尝胆，厚积薄发。

Labyrinth

Date: Wed Oct 17 08:09:36 CST 2018

In Category: NoCategory

Description：

给出一个四联通的 $N\times M$ 网格图和起点。图中有一些位置是障碍物。

现在上下移动步数不限，向左至多走 $ a$ 步，向右至多走 $ b$ 步，求从起点出发能到达多少个空地。

$N,M\leqslant 2000$

## Solution：

开始的想法是直接跑最短路，发现矛盾在于，如果到一个格子向左走的步数较少，向右走的步数较多，以及这种情况反过来，无法确定那种更优，进而无法确定用那种状态更新接下来的点。

但是实际上这种情况是不存在的。考虑要从点 $ U $ 到达 $ V $ ，横向的差值为是固定的。

也就是说，任何一个合法的方案向左走的步数减掉向右走的步数都应该等于 $ 2$ 。

那么这种矛盾不存在了。因为向左向右的步数会同时增长，否则一定不会到达这个目标点。

Code：


#include<bits/stdc++.h>

using namespace std;

char getc()

{

	register char c = getchar();

	while(c != '.' && c != '*')c = getchar();

	return c;

}

int n,m;

#define MAXN 2010

char c[MAXN][MAXN];

int sx,sy;

int ml,mr;

struct st

{

	int l,r;

	bool operator < (st b)const

	{

		return l > b.l;

	}

	bool operator > (st b)const

	{

		return l > b.l;

	}

}d[MAXN * MAXN];

int to(int i,int j){return (i - 1) * m + j;}

bool v[MAXN * MAXN];

#define fi first

#define se second

int main()

{

	scanf("%d%d",&n,&m);

	scanf("%d%d",&sx,&sy);

	scanf("%d%d",&ml,&mr);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			c[i][j] = getc();

	memset(d,0x3f,sizeof(d));

	d[to(sx,sy)] = (st){0,0};

	priority_queue< pair<st,pair<int,int> > > q;

	q.push(make_pair((st){0,0},make_pair(sx,sy)));

	while(!q.empty())

	{

		pair<int,int> k = q.top().second;q.pop();

		if(v[to(k.fi,k.se)])continue;

		v[to(k.fi,k.se)] = true;

		st dis = d[to(k.fi,k.se)];

		if(k.fi != 1 && c[k.fi - 1][k.se] != '*')

		{

			if(d[to(k.fi - 1,k.se)] > dis)

			{

				d[to(k.fi - 1,k.se)] = dis;

				q.push(make_pair(d[to(k.fi - 1,k.se)],make_pair(k.fi - 1,k.se)));

			}

		}

		if(k.fi != n && c[k.fi + 1][k.se] != '*')

		{

			if(d[to(k.fi + 1,k.se)] > dis)

			{

				d[to(k.fi + 1,k.se)] = dis;

				q.push(make_pair(d[to(k.fi + 1,k.se)],make_pair(k.fi + 1,k.se)));

			}

		}

		if(k.se != 1 && c[k.fi][k.se - 1] != '*')

		{

			if(d[to(k.fi,k.se - 1)] > (st){dis.l + 1,dis.r})

			{

				d[to(k.fi,k.se - 1)] = (st){dis.l + 1,dis.r};

				q.push(make_pair(d[to(k.fi,k.se - 1)],make_pair(k.fi,k.se - 1)));

			}

		}

		if(k.se != m && c[k.fi][k.se + 1] != '*')

		{

			if(d[to(k.fi,k.se + 1)] > (st){dis.l,dis.r + 1})

			{

				d[to(k.fi,k.se + 1)] = (st){dis.l,dis.r + 1};

				q.push(make_pair(d[to(k.fi,k.se + 1)],make_pair(k.fi,k.se + 1)));

			}

		}

	}

	int ans = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(d[to(i,j)].l <= ml && d[to(i,j)].r <= mr)

			{

				++ans;

			}

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 图论-dijkstra

wjh15101051