当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3182:The Grove

题目描述
The pasture contains a small, contiguous grove of trees that has no 'holes' in the middle of the it. Bessie wonders: how far is it to walk around that grove and get back to my starting position? She's just sure there is a way to do it by going from her start location to successive locations by walking horizontally, vertically, or diagonally and counting each move as a single step. Just looking at it, she doesn't think you could pass 'through' the grove on a tricky diagonal. Your job is to calculate the minimum number of steps she must take.

Happily, Bessie lives on a simple world where the pasture is represented by a grid with R rows and C columns (1 <= R <= 50, 1 <= C <= 50). Here's a typical example where '.' is pasture (which Bessie may traverse), 'X' is the grove of trees, '*' represents Bessie's start and end position, and '+' marks one shortest path she can walk to circumnavigate the grove (i.e., the answer):

...+...

..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*
The path shown is not the only possible shortest path; Bessie might have taken a diagonal step from her start position and achieved a similar length solution. Bessie is happy that she's starting 'outside' the grove instead of in a sort of 'harbor' that could complicate finding the best path.
输入解释
Line 1: Two space-separated integers: R and C

Lines 2..R+1: Line i+1 describes row i with C characters (with no spaces between them).
输出解释
Line 1: The single line contains a single integer which is the smallest number of steps required to circumnavigate the grove.
输入样例
6 7
.......
...X...
..XXX..
...XXX.
...X...
......*
输出样例
13

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3182

最后修改于 2020-10-29T06:55:07+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536