P0771

[Usaco2006 Jan] The Grove 树木

[Usaco2006 Jan] The Grove 树木

牧场中有一片连续的树林，树林内部没有空洞。贝茜想知道，从起点出发，绕树林行走一周并回到起点，最少需要多少步。

贝茜每次可以沿水平方向、竖直方向或对角线方向移动到相邻位置，每次移动计为 11 步。她不能穿过树林，包括沿对角线从树林中穿过。

牧场由一个 RR 行 CC 列的网格表示。地图中，. 表示贝茜可以通行的空地，X 表示树林，* 表示贝茜的起点和终点。题目保证一定存在可行的最短路径。

时间限制：5000 ms5000\ \mathrm{ms}。
内存限制：65536 KB65536\ \mathrm{KB}。

输入格式

第一行输入两个整数 RR 和 CC。

接下来 RR 行，每行包含 CC 个字符，表示牧场地图，字符之间没有空格。

输出格式

输出一个整数，表示贝茜绕树林行走一周并回到起点所需的最少步数。

样例输入

6 7
.......
...X...
..XXX..
...XXX.
...X...
......*

样例输出

13

数据范围

  • 1≤R≤501\le R\le 50；
  • 1≤C≤501\le C\le 50；
  • 题目保证存在可行的最短路径。

来源与许可

本题为 USACO 2006 January 试题「The Grove」，题面与测试数据整理自 BZOJ 1656。

样例 1

输入

6 7
.......
...X...
..XXX..
...XXX.
...X...
......*

输出

13