Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
?
?
Input
The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ ?? express Merceki initial position.
‘#’ forbid road;
‘.’ Road.
‘@’ KCF
?
?
Output
For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
?
?
Sample Input
4 4 Y.#@ .... .#.. @..M 4 4 Y.#@ .... .#.. @#.M 5 5 Y..@. .#... .#... @..M. #...#
?
?
Sample Output
66 88 66
先找到Y和M,再分別對他們廣度優先搜索肯德基店,用兩個二維數組記錄步數
最后遍歷兩個記錄步數的二維數組,選擇到肯德基店距離之和最近的店
注意:有的肯德基店可能根本到不了,所以要判零,排除去不了的,防住影響結果
ac代碼:
#include<stdio.h>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=200;
int n,m,ex,ey,sx,sy;
char mp[N+5][N+5];
int ef[N+5][N+5],sf[N+5][N+5];
int visit[N+5][N+5];
int tx[4]={1,0,-1,0};
int ty[4]={0,-1,0,1};
struct node{int x,y,step;
};
void bfs(int x,int y,int flag)
{memset(visit,0,sizeof(visit));queue<node> que;node q,p;p.x=x,p.y=y;p.step=0;que.push(p);visit[x][y]=1;while(!que.empty()){p=que.front();que.pop();//彈出for(int i=0;i<4;i++){q=p;q.x+=tx[i];q.y+=ty[i];if(mp[q.x][q.y]!='#'&&visit[q.x][q.y]!=1&&q.x>=0&&q.x<n&&q.y>=0&&q.y<m){visit[q.x][q.y]=1;q.step++;if(flag==1)//記錄Y的ef[q.x][q.y]=q.step;if(flag==0)//記錄M的sf[q.x][q.y]=q.step;que.push(q);//壓入}}}return ;
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){memset(mp,0,sizeof(mp));memset(ef,0,sizeof(ef));memset(sf,0,sizeof(sf));for(int i=0;i<n;i++)scanf("%s",&mp[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(mp[i][j]=='Y')ex=i,ey=j;else if(mp[i][j]=='M')sx=i,sy=j;}bfs(ex,ey,1);//分別廣搜bfs(sx,sy,0);int min=10000000;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(mp[i][j]=='@')//是肯德基店if(ef[i][j]!=0&&sf[i][j]!=0)//注意去不了的肯德基店要跳過if(ef[i][j]+sf[i][j]<min)min=ef[i][j]+sf[i][j];printf("%d\n",min*11);}return 0;
}?
)
)
