1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
|
#include<stdio.h> #include<string.h> #include<iostream> #include<queue> #define inf 0xffffff using namespace std; const int N=210; int m,n,mark[N][N],dis[N][N][2],dir[4][2]={1,0, 0,1, -1,0, 0,-1},flag; char s[N][N]; struct node{ int x,y,step; }; bool judge(int x,int y){ if(x>=0 && x<m && y>=0 && y<n && s[x][y]!='#' && mark[x][y]==0) return 1; return 0; } void bfs(int x,int y){ int k; queue<node>q; node cur,next; cur.x=x;cur.y=y;cur.step=0; mark[x][y]=1; q.push(cur); while(!q.empty()){ cur=q.front(); q.pop(); next.step=cur.step+1; for(k=0;k<4;k++){ next.x=x=cur.x+dir[k][0]; next.y=y=cur.y+dir[k][1]; if(judge(x,y)){ mark[x][y]=1; if(s[x][y]=='@')dis[x][y][flag]=next.step; q.push(next); } } } } int main(){ int i,j,min; while(scanf("%d %d",&m,&n)!=-1){ min=inf; for(i=0;i<m;i++) for(j=0;j<n;j++) dis[i][j][0]=dis[i][j][1]=inf;
for(i=0;i<m;i++)scanf("%s",s[i]); for(i=0;i<m;i++) for(j=0;j<n;j++){ if(s[i][j]=='Y'){ flag=0; memset(mark,0,sizeof(mark)); bfs(i,j); } else if(s[i][j]=='M'){ flag=1; memset(mark,0,sizeof(mark)); bfs(i,j); } }
for(i=0;i<m;i++) for(j=0;j<n;j++) if(s[i][j]=='@' && min>dis[i][j][0]+dis[i][j][1]) min=dis[i][j][0]+dis[i][j][1]; printf("%dn",min*11); } return 0; }
|
近期评论