HDU 2612 Find a way BFS，防止超时是关键

之前我写的时候是：每找到一个‘@’就广搜一次，如果这样写有多少个‘@’就会广搜几次，这样就超时了。我队友告诉我应该打个表，这个方法确实不错。因为'Y'和'M'是唯一的，我通过这两个点分别广搜一次，对所有到达‘@’的情况打个表，这样就节省了很多时间。具体看代码吧。

#include<cstdio>
#include<stdio.h>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define INF 0x3f3f3f3f
#define MAX 1005
using namespace std;
int n,m,vis[MAX][MAX],v[4][2]= {{0,1},{0,-1},{1,0},{-1,0}},Time[MAX][MAX],b[MAX][MAX];
char Map[MAX][MAX];
struct node
{
int x,y,step;
};
void BFS(int sx,int sy)
{
memset(vis,0,sizeof(vis));
queue<node>Q;
node a,next;
a.x=sx;
a.y=sy;
a.step=0;
Q.push(a);
vis[sx][sy]=1;
while(!Q.empty())
{
a=Q.front();
Q.pop();
if(Map[a.x][a.y]=='@' && !b[a.x][a.y])//数组b记录是否到达过这个‘@’

{
b[a.x][a.y]=1;
Time[a.x][a.y]+=a.step*11;
next.x=sx;
next.y=sy;
next.step=0;
Q.push(next);
}
for(int i=0; i<4; i++)
{
next.x=a.x+v[i][0];
next.y=a.y+v[i][1];
if(next.x>=0 && next.x<n && next.y>=0 && next.y<m && Map[next.x][next.y]!='#' && !vis[next.x][next.y])
{
vis[next.x][next.y]=1;
next.step=a.step+1;
Q.push(next);
}
}
}
}
int main()
{
int i,j,ans,x1,x2,y1,y2;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=INF;
for(i=0; i<n; i++)
{
scanf("%s",Map[i]);
}
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
if(Map[i][j]=='Y')
{
x1=i;
y1=j;
}
if(Map[i][j]=='M')
{
x2=i;
y2=j;
}
}
}
memset(b,0,sizeof(b));
memset(Time,0,sizeof(Time));
BFS(x1,y1);//对‘Y’到达‘@’进行广搜
memset(b,0,sizeof(b));
BFS(x2,y2);对‘M’到达‘@’进行广搜
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(Time[i][j]!=0)
ans=min(ans,Time[i][j]);
}
}
printf("%dn",ans);
}
return 0;
}