F. 1-04E. zzj & liaoy 想要去摄影

内存限制:512 MiB 时间限制:1125 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

摄影是liaoy的一大爱好,碰巧zzj也很感兴趣。于是他们打算这个周末从交大出发,到西安市内中意的一些地点去摄影。zzj和liaoy想要知道他们这次活动最少需要走多少路程(不需要返程)。

西安市的地图可以视作为一个 的矩形网格图,图上标注了交大的位置(起点)、空地、墙壁、计划地点。墙壁是不可通行的,其他地形都是可通行的。zzj和liaoy从交大出发,每一步可以选择上下左右四个方向移动,目标是到达每个计划地点至少一次,求达成该目标所需的最少步数。

输入格式

第一行两个正整数 ,表示地图的大小。

接下来一共是 的字符串,表示地图的详细地形,其中'p'表示交大的位置,'.'表示空地,'#'表示不可通过的墙,'@'表示一个计划地点。

输出格式

输出一行一个非负整数,表示达成目标所需的最少步数。

如果他们不可能完成摄影计划,则输出

样例

样例输入1

2 4
.p..
@##@

样例输出1

7

样例输入2

3 3
#@#
#p@
@.#

样例输出2

6

数据范围与提示

地图上至少存在一个计划地点,且计划地点的数量不超过 个。

Hint

数据范围不算太大,时间复杂度不卡常数。