bzoj 1671: [Usaco2005 Dec]Knights of Ni 骑士【bfs】

bfs预处理出每个点s和t的距离d1和d2（无法到达标为inf），然后在若干灌木丛格子(x,y)里取min(d1[x][y]+d2[x][y])

/*

  0：贝茜可以通过的空地

    1：由于各种原因而不可通行的区域

    2：贝茜现在所在的位置

    3：骑士们的位置

    4：长着贝茜需要的灌木的土地

*/

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int N=1005,inf=1e9,dx[]={-1,1,0,0},dy[]={0,0,-1,1};

int n,m,a[N][N],d1[N][N],d2[N][N],ans=inf;

bool v[N][N];

struct qwe

{

	int x,y,p;

	qwe(int X=0,int Y=0,int P=0)

	{

		x=X,y=Y,p=P;

	}

}s,t;

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

bool ok(int x,int y)

{

	return x>=1&&x<=n&&y>=1&&y<=m&&!v[x][y]&&a[x][y]!=1;

}

void bfs(qwe s)

{

	queue<qwe>q;

	memset(v,0,sizeof(v));

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

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

			d2[i][j]=inf;

	v[s.x][s.y]=1;

	d2[s.x][s.y]=0;

	q.push(s);

	while(!q.empty())

	{

		qwe u=q.front();

		q.pop();

		for(int i=0;i<4;i++)

			if(ok(u.x+dx[i],u.y+dy[i]))

			{

				v[u.x+dx[i]][u.y+dy[i]]=1;

				d2[u.x+dx[i]][u.y+dy[i]]=u.p+1;

				q.push(qwe(u.x+dx[i],u.y+dy[i],u.p+1));

			}

	}

}

int main()

{

	m=read(),n=read();

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

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

		{

			a[i][j]=read();

			if(a[i][j]==2)

				s=qwe(i,j,0);

			if(a[i][j]==3)

				t=qwe(i,j,0),a[i][j]=1;

		}

	bfs(s);

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

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

			d1[i][j]=d2[i][j];

	a[t.x][t.y]=3;

	bfs(t);

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

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

			if(a[i][j]==4)

				ans=min(ans,d1[i][j]+d2[i][j]);

	printf("%d\n",ans);

	return 0;

}

巴特西

bzoj 1671: [Usaco2005 Dec]Knights of Ni 骑士【bfs】

最新文章

热门文章