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

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<queue>  6 #define INF 0x3f3f3f3f    7 using namespace std;  8 struct node  9 { 10     int x; 11     int y; 12     int step; 13 }; 14 char g[205][205]; 15 int stepA[205][205]; 16 int stepB[205][205]; 17     queue<node>q; 18 int yx, yy, mx, my;  19 int x, y; 20 long long ans; 21 int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; 22  23 int main() 24 { 25 //    freopen("in.in","r",stdin); 26 //    freopen("out.txt","w",stdout); 27     while(scanf("%d%d",&x,&y)!=EOF) 28     { 29         memset(g,0,sizeof(g)); 30         memset(stepA,-1,sizeof(stepA)); 31         memset(stepB,-1,sizeof(stepB)); 32         char tmp[205]; 33         for(int i = 1; i <= x; i++) 34         { 35             scanf("%s",tmp); 36             for(int j = 1; j <= y; j++) 37             { 38                 if(tmp[j-1]==‘Y‘) 39                 { 40                     yx = i; 41                     yy = j; 42                 } 43                 if(tmp[j-1]==‘M‘) 44                 { 45                     mx = i; 46                     my = j; 47                 } 48                 g[i][j] = tmp[j-1]; 49             } 50         } 51         ans = INF; 52  53         node s, t; 54      55         s.x = yx; 56         s.y = yy; 57         s.step = 0; 58         q.push(s); 59         while(q.size()) 60         { 61             s = q.front(); 62             q.pop(); 63             stepA[s.x][s.y] = s.step; 64             for(int i = 0; i < 4; i++) 65             { 66                 t.x = s.x + d[i][0]; 67                 t.y = s.y + d[i][1]; 68                 t.step = s.step + 1; 69                 if(stepA[t.x][t.y] != -1)    continue; 70                 if(g[t.x][t.y]==‘.‘|| g[t.x][t.y]==‘@‘) 71                     q.push(t); 72             } 73         } 74         s.x = mx; 75         s.y = my; 76         s.step = 0; 77         q.push(s); 78         while(q.size()) 79         { 80             s = q.front(); 81             q.pop(); 82             stepB[s.x][s.y] = s.step; 83             for(int i = 0; i < 4; i++) 84             { 85                 t.x = s.x + d[i][0]; 86                 t.y = s.y + d[i][1]; 87                 t.step = s.step + 1; 88                 if(stepB[t.x][t.y] != -1)    continue; 89                 if(g[t.x][t.y]==‘.‘|| g[t.x][t.y]==‘@‘) 90                     q.push(t); 91             } 92         } 93         for(int i = 1; i <= x; i++) 94         { 95             for(int j = 1; j <= y; j++) 96             { 97                 if(g[i][j]==‘@‘ && stepA[i][j]+stepB[i][j]<ans && stepA[i][j]!=-1 && stepB[i][j]!=-1) 98                     ans = stepA[i][j]+stepB[i][j]; 99             }            100         }101         cout<<ans*11<<endl;102     }103     104     return 0;105 }