P2976 [USACO10JAN]船舶周围的一个岛屿Shipping Around an Island

    • 20通过
    • 61提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2010 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Farmer John decided to start his own cruise ship line! He has but one ship, but is hoping for big growth. He recently acquired a map of the area of ocean where his cruise ship will operate. It looks something like the diagram below, with height H (3 <= H <= 1000) and width W (3 <= W <= 1000).

    ................... 
    ................... 
    .....A............. 
    .....A..x.......... 
    ..x..A.....AAAA.... 
    .....A.....A..A.... 
    .....AAAAAAAA.A.... 
    ........A.....A.... 
    .xx...AAA...x.A.... 
    ......A............ 
    ...AAAAAAAAAAAAA... 
    ................... 

    In this map, '.' denotes water; 'A' is an element of the main island; and 'x' are other islands.

    Farmer John has decided his cruise ship will loop around the main island. However, due to trade restrictions, the path his ship takes is NOT allowed to go around any OTHER islands. For instance, the following path of length 50 is not allowed because it encloses the island denoted by 'x'.

    ................... 
    ....+--+........... 
    ....|A.|........... 
    ....|A.|x.+-----+.. 
    ..x.|A.+--+AAAA.|.. 
    ....|A.....A..A.|.. 
    ....|AAAAAAAA.A.|.. 
    ....|...A.....A.|.. 
    .xx.|.AAA...x.A.|..    <--- route circumnavigates 'x' -- illegal! ..+-+.A.........|.. 
    ..|AAAAAAAAAAAAA|.. 
    ..+-------------+.. 

    Given a map, help Farmer John determine the shortest path his cruise ship can take to go around the main island without going around any other islands.

    Two cells are considered connected if they lie vertically or

    horizontally across from one another (not diagonally). It is

    guaranteed that the main island is connected and that a solution exists.

    Note that FJ's path may visit the same square more than once, for instance there are three squares that are visited more than once in FJ's optimal path (of length 62) for the example:

    ................... 
    ....+--+........... 
    ....|A.|........... 
    ....|A.|x.+----+... 
    ..x.|A.+--+AAAA|... 
    ....|A.....A..A|... 
    ....|AAAAAAAA.A|... 
    ....|...A..+-+A|... 
    .xx.|.AAA..|x|A|... 
    ..+-+.A....+-+-++.. 
    ..|AAAAAAAAAAAAA|.. 
    ..+-------------+.. 

    The above diagram is somewhat unclear because of the path overlapping itself. Drawn in two stages, FJ's optimal path is:

    ...................            ................... 
    ...................            ....+--+........... 
    .....A.............            ....|A.|........... 
    .....A..x..........            ....|A.|x.+----+... 
    ..x..A.....AAAA....            ..x.|A.+--+AAAA|... 
    .....A.....A..A....  and then  ....|A.....A..A|... 
    .....AAAAAAAA.A....            ....|AAAAAAAA.A|... 
    ....V...A..+>.A....            ....V...A...>+A|... 
    .xx.|.AAA..|x.A....            .xx...AAA...x|A|... 
    ..+-+.A....+----+..            .....A.......+-+... 
    ..|AAAAAAAAAAAAA|..            ...AAAAAAAAAAAAA... 
    ..+-------------+..            ................... 

    John得到一份地图,长H(3<=H<=1000)宽W(3<=W<=1000),地图中’.’表示水,’A’表示大陆,’x’表示其他小岛。他决定驾驶他的船绕大陆一圈,但并不想环绕其他小岛。John可以再任意有水的格子出发,求绕一周最小路径长度(一个格子可以经过任意多次)。

    输入格式:

    第一行两个空格隔开正整数H和W(3<=H,W<=1000),接下来有H行,每行W个字符表示地图。

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: H and W

    * Lines 2..H+1: Line i+1 contains contains W characters that are the elements of map row i (all '.' or 'x' or 'A')

    输出格式:

    * Line 1: The minimum length of a path that Farmer John's cruise ship can take

    输入输出样例

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