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