BFS求助
查看原帖
BFS求助
229957
Wu_while楼主2021/9/7 11:06
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,ans;
char ch;
int tx,ty,sx,sy;
int p[20000];
int a[20000];
bool v[20000];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int ddx[8]={-1,1,0,0,-1,-1,1,1};
int ddy[8]={0,0,-1,1,-1,1,-1,1};
int f(int x,int y)
{
	return (x-1)*m+y;
}
struct point
{
	int x;
	int y;
	int s;
};
void init()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[f(i,j)]=p[f(i,j)];
	memset(v,0,sizeof(v));
	ans=0x3f3f3f3f;
}
void bfs()
{
	queue<point> q;
	point t,u;
	t.x=sx;
	t.y=sy;
	t.s=0;
	q.push(t);
	while(!q.empty())
	{
		t=q.front();
		q.pop();
		v[f(t.x,t.y)]=1;
		if(a[f(t.x,t.y)]==2)
			ans=min(ans,t.s);
		for(int i=0;i<4;i++)
		{
			int xx=t.x+dx[i],yy=t.y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[f(xx,yy)]!=1&&!v[f(xx,yy)])
			{
				u.x=xx;
				u.y=yy;
				u.s=t.s+1;
				q.push(u);
			}
		}
	}
}
void work()
{
	if(sx==tx&&sy==ty)
	{
		printf("0\n");
		return;
	}
	init();
	a[f(tx,ty)]=2;
	for(int i=0;i<8;i++)
	{
		int xx=tx+ddx[i],yy=ty+ddy[i];
		while(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[f(xx,yy)]!=1)
		{
			a[f(xx,yy)]=2;
			xx+=ddx[i];
			yy+=ddy[i];
		}
	}
	bfs();
	if(ans==0x3f3f3f3f)
		printf("Poor Harry\n");
	else
		printf("%d\n",ans);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>ch;
			if(ch=='X')
				p[f(i,j)]=1;
		}
	while(cin>>tx>>ty>>sx>>sy&&tx&&ty&&sx&&sy)
		work();
	return 0;
}

40pts40pts,五个TLE,一个MLE

2021/9/7 11:06
加载中...