TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3741
  • 题目
  • P3741噩梦
    限制 : 时间限制 : 1000 MS   空间限制 : 165536 KB
    评测说明 : 时限1000ms
    问题描述

      昨晚,约翰做了一个噩梦,他梦见他和奶牛贝西被困在了一个巨大的迷宫里面。更惨的是,迷宫里面有两个火山口,它们会往外喷出岩浆,岩浆四处蔓延,遇到岩浆会有生命危险。约翰和贝西在迷宫中所处的位置不同,约翰想知道,他能否活着见到贝西。
      迷宫呈网格状,约翰和贝西都可以往上下左右四个方向移动,每一秒,约翰可以移动三步,贝西只能移动一步。每个格子的岩浆都在不断往四周蔓延(上下左右),每一秒会蔓延到以当前位置为中心,距离2步以内的所有格子。
      每一秒,岩浆先蔓延,然后才是约翰和贝西移动。如果约翰或者贝西到达的格子已被岩浆占领,就会有生命危险。  

    输入格式

    第一行,两个整数n和m,表示迷宫的尺寸(1<n,m<800)
    接下来,一个n*m的字符矩阵,表示迷宫,其中:
    '.'表示该处是空地,约翰、贝西、岩浆都可以通过
    'X'表示该处是障碍,只有岩浆可以通过,约翰和贝西无法通过
    'M'表示开始时约翰的位置
    'G'表示开始时贝西的位置
    'Z'表示开始时火山口的位置
    一开始,矩阵中只有两个Z,一个M和一个G,行末无空格,最后一行有回车。
    注意,每一秒,约翰和贝西可以选择走,也可以选择原地停留。如果选择走,约翰必须走满三步。

    输出格式

    一行,一个整数,表示约翰找到贝西所需最少时间。
    如果无法活着见到贝西,输出-1

    样例输入 1

    5 6
    XXXXXX
    XZ..ZX
    XXXXXX
    M.G...
    ......

    样例输出 1

    1

    样例输入 2

    5 6
    XXXXXX
    XZZ..X
    XXXXXX
    M.....
    ..G...

    样例输出 2

    1

    样例输入 3

    10 10
    ..........
    ..X.......
    ..M.X...X.
    X.........
    .X..X.X.X.
    .........X
    ..XX....X.
    X....G...X
    ...ZX.X...
    ...Z..X..X

    样例输出 3

    -1


    来源  hdu 3085