问题描述
不知不觉几年没见了,恰逢中秋假期好兄弟灏森从广州过来游玩,李老师答应了好好招待他。
灏森到了深圳后住在了南山区一个酒店,刚入住就迫不及待地要李老师约见面请客,于是两个大男人在中秋前夕进行了一场约会,噢,不是,是聚会。他们约好了一起去吃烧烤。深圳这边的烧烤店太多了,他们都很懒,所以一致同意找一家让两个人到达所花总步数最少的烧烤店。
现在给你一张深圳地图,灏森和李老师都可以向上、向下、向左、向右移动一格。
题目输入
第1行,两个整数n,m (2<=n,m<=200)。
接下来n行,每一行包含m个字符。
“Y”表示李老师的初始位置;
“M”表示灏森的初始位置;
“#”表示不能通行的道路;
“.”表示可通行的道路;
“@”表示烧烤店。
题目输出
输出灏森和李老师到达其中一家烧烤店所需的最少总步数。最后李老师如愿请客了,所以你可以放心,总有一个烧烤店可以让他们见面。
样例输入
4 4
Y.#@
....
.#..
@..M
样例输出
6