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

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int inf=99999999;
char map[220][220];
int cnt[2][220][220];
int flag[220][220];
int tmove[4]= {1,-1,0,0};
struct node {
    int n,m;
} a[220];
int H,W;
int Yn,Ym,Mn,Mm;
int x;
void bfs(int n,int m,int who) {
    node t;
    t.n=n,t.m=m;
    queue<node>q;
    flag[n][m]=1;
    cnt[who][n][m]=0;
    q.push(t);
    while(!q.empty()) {
        t=q.front();
        for(int i=0; i<4; i++) {
            int tn=t.n+tmove[i],tm=t.m+tmove[(i+2)%4];
            if(tn>=0&&tn<H&&tm>=0&&tm<W&&!flag[tn][tm]&&map[tn][tm]!='#') {
                flag[tn][tm]=1;
                if(cnt[who][tn][tm]==inf)
                    cnt[who][tn][tm]=cnt[who][t.n][t.m]+1;
                else
                    cnt[who][tn][tm]+=cnt[who][t.n][t.m]+1;
                node temp;
                temp.n=tn,temp.m=tm;
                q.push(temp);
            }
        }
        q.pop();
    }
}
int main() {
    while(scanf("%d %d",&H,&W)!=EOF) {
        getchar();
        x=0;
        for(int i=0; i<H; i++) {
            for(int j=0; j<W; j++) {
                cnt[0][i][j]=cnt[1][i][j]=inf;
                map[i][j]=getchar();
                if(map[i][j]=='@')
                    a[x].n=i,a[x++].m=j;
                else if(map[i][j]=='Y')
                    Yn=i,Ym=j;
                else if(map[i][j]=='M')
                    Mn=i,Mm=j;
            }
            getchar();
        }
        memset(flag,0,sizeof(flag));
        bfs(Yn,Ym,0);
        memset(flag,0,sizeof(flag));
        bfs(Mn,Mm,1);
        int res=inf;
        for(int i=0; i<x; i++)
            if(res>cnt[0][a[i].n][a[i].m]+cnt[1][a[i].n][a[i].m])
                res=cnt[0][a[i].n][a[i].m]+cnt[1][a[i].n][a[i].m];
        printf("%d\n",res*11);
    }
    return 0;
}