问题 4741 --胖瑜走公园

4741: 胖瑜走公园

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

胖瑜在游玩公园,公园的是R排,C列组成的,如下图所示:
.......
...X...
..XXX..
...XXX.
...X...
......*
*代表的是胖瑜所在位置,X代表的是树,.代表的是能走的路,现在想知道胖瑜能绕着所有的树走一圈回到开始*的位置需要的最少步数是多少。每一步可以上下左右对角线,共8个方向走。她不能对角线穿过小树林,所有的树都是上或者下或者左或者右的链接在一起的,没有独立不相连的两堆存在。在下图中+就是代表她走的路线一共走了13步。
...+...
..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*

输入

第一行输入R,C(1 <= R <= 50, 1 <= C <= 50).
下面R行每行是一字符串,中间没有空格。

输出

满足题意的最少步数。

样例输入

6 7<br/>.......<br/>...X...<br/>..XXX..<br/>...XXX.<br/>...X...<br/>......*

样例输出

13

来源

[提交][状态]