Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5401 Accepted Submission(s):
1823
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define MAX 210
#define INF 0x3f3f3f
using namespace std;
int bu1[MAX][MAX];//记录第一个人步数
int bu2[MAX][MAX];//记录第二个人步数
int p;
char map[MAX][MAX];
int vis[MAX][MAX];
int n,m;
struct node
{
int x,y;
int step;
};
int MIN(int x,int y)
{
return x<y?x:y;
}
void bfs(int x1,int y1,int p)
{
memset(vis,0,sizeof(vis));
int j,i,ok=0;
int move[4][2]={0,1,0,-1,1,0,-1,0};
queue<node>q;
node beg,end;
beg.x=x1;
beg.y=y1;
beg.step=0;
q.push(beg);
while(!q.empty())
{
end=q.front();
q.pop();
if(map[end.x][end.y]==‘@‘)//遇见@则表示到达终点
{
if(p==1)
bu1[end.x][end.y]=end.step;
else
bu2[end.x][end.y]=end.step;
}
for(i=0;i<4;i++)
{
beg.x=end.x+move[i][0];
beg.y=end.y+move[i][1];
if(!vis[beg.x][beg.y]&&0<=beg.x&&beg.x<n&&0<=beg.y&&beg.y<m&&map[beg.x][beg.y]!=‘#‘)
{
vis[beg.x][beg.y]=1;
beg.step=end.step+11;
q.push(beg);
}
}
}
}
int main()
{
int sum,j,i,t,k,x1,x2,y1,y2,min;
int s[11000];
while(scanf("%d%d",&n,&m)!=EOF)
{
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;
}
else if(map[i][j]==‘M‘)
{
x2=i;y2=j;
}
}
}
memset(bu1,INF,sizeof(bu1));
bfs(x1,y1,1);
memset(bu2,INF,sizeof(bu2));
bfs(x2,y2,2);
min=INF;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(bu1[i][j]!=INF&&bu2[i][j]!=INF)
{
min=MIN(bu1[i][j]+bu2[i][j],min);//取两者步数和的最小值
}
}
}
printf("%d\n",min);
}
return 0;
}
原文:http://www.cnblogs.com/tonghao/p/4590972.html