Problem Description

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 1111 minutes.

Input

The input contains multiple test cases.
Each test case include, first two integers n,m.(2<=n,m<=200)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

Translation

给一张地图，两个人分别处在标为’Y’和’M’的位置，要走到同一家肯德基（标为’@‘）。标为’.‘的格点表示可走，标为’#'的格点表示不可走，两个人只能走上下左右四个方向，每走一步花费11分钟。问两人至少花费多少时间在一家肯德基会和（两个人是分开走的，也就是说只有一个人到达，另一个人才会出发）。

Idea

一种简单想法是枚举所有的KFC，找到其中花费的最少时间，如果图很大，KFC又均匀得分布在图上，显然会TLE。
于是换一种思路，仅用两次BFSBFS记录 ‘Y’‘M’两点分别到地图上各个点的最短路径长度，然后查询每一个KFC的花费即可。

Code

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=203;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int n,m;
int step[2][N][N];//存步数
bool vis[N][N];
struct state
{
	int x,y;
};
state start_a,start_b;
char map[N][N];//存地图
void init()//初始化
{
	memset(step,0,sizeof(step));
}
void bfs(state start,int step[N][N])
{
	memset(vis,0,sizeof(vis));//归零
	queue<state>q;
	q.push(start);
	vis[start.x][start.y]=1;
	while(!q.empty())
	{
		state now,nxt;
		now=q.front();
		int i;
		for(i=0;i<n;i++)
		{
			nxt.x=now.x+dx[i];
			nxt.y=now.y+dy[i];
			if(nxt.x<1||nxt.x>n) continue;
			else if(nxt.y<1||nxt.y>m) continue;
			else if(vis[nxt.x][nxt.y]) continue;
			else if(map[nxt.x][nxt.y]=='#') continue;
			else
			{
				//走到下一个节点，步数增加1。
				step[nxt.x][nxt.y]=step[now.x][now.y]+1;
				vis[nxt.x][nxt.y]=1;//标记访问
				q.push(nxt);
			}
		}
		q.pop();//出队
	}
}
void solve()
{
	init();
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>map[i][j];
			switch(map[i][j])//记录两个起点
			{
				case 'Y':
					start_a.x=i;
					start_a.y=j;
					break;
				case 'M':
					start_b.x=i;
					start_b.y=j;
					break;
				default: break;		
			}
		}
	}
	int ans=0x3f3f3f3f;
	bfs(start_a,step[0]);
	bfs(start_b,step[1]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			//如果step为0，说明不能走到该KFC。
			if(map[i][j]=='@'&&step[0][i][j]&&step[1][i][j])
			{
				ans=min(ans,step[0][i][j]+step[1][i][j]);
			}
		}
	}
	cout<<ans*11<<endl;
}
int main()
{
	while(cin>>n>>m) solve();
	return 0;
}