P2864 [USACO06JAN]树林The Grove

    • 86通过
    • 240提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS USACO 2006 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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.

    牧场里有一片树林,林子里没有坑.

    贝茜很想知道,最少需要多少步能围绕树林走一圈,最后回到起点.她能上下左右走,也能 走对角线格子.

    牧场被分成R行C列(1 <= R =< 50,1 < =C<= 50).下面是一张样例的地图,其中表示贝茜 可以走的空地,“X”表示树林,表示起点.而贝茜走的最近的路已经特别地用“ + ”表示 出来.

    题目保证,最短的路径一定可以找到.

    输入输出格式

    输入格式:

    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.

    输入输出样例

    输入样例#1: 复制
    6 7
    .......
    ...X...
    ..XXX..
    ...XXX.
    ...X...
    ......*
    输出样例#1: 复制
    13
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。