伯罗奔尼撒战争是以雅典为首的提洛同盟与以斯巴达为首的伯罗奔尼撒联盟之间的一场战争。这场战争从前431年一直持续到前404年，使得绝大多数周边城邦必须加入其中一方的阵营。战争第一阶段（BC431-BC421），雅典在伯里克利的领导之下，凭借强大的海军，采取陆地上防御在海上进攻的策略。而斯巴达在阿基达摩斯二世的领导之下，率领它令人畏惧的战士进行陆地强攻。两个强邦侧重点不同的军事力量导致了战争第一阶段的僵持局面。

话说，有一天阿基达摩斯二世决定率兵进攻雅典的一个居民点阿提卡，当他们满怀斗志的奔向阿提卡的时候，殊不知他们正走向伯利克里所设下的迷宫陷阱之中。当他们发现时，已为时已晚。

As you know, the Magpie Festival is comging!

为了早日返回斯巴达，阿基达摩斯二世立即让所有的斯巴达勇士去需找迷宫的出口 E 。现在他们被困在迷宫的 S 点，迷宫中.表示空地，可以通过，#表示墙，不能通过，每次只能向上下左右四个方向移动，每个勇士每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度和方向相同。现在请你计算一下他们所有人要找到迷宫的出口，最少需要时间之和是多少。

PS：假设迷宫中每个点可以容纳的人数没有限制。

第一行输入三个数 n,m,c ,(2 \le m \le n \le 500,100 \le c \le 10000)分别代表迷宫的长度和宽度，以及被困迷宫的斯巴达勇士数（不包括阿基达摩斯二世）。

下面 m 行每行有 n 个字符用来表示迷宫地图。

详细输入格式见样例。

输出一个整数，表示找到迷宫出口时，所有勇士消耗的最短时间之和，如不能找到出口输出 -1 。

广搜

广搜