P2199 最后的迷宫

    • 273通过
    • 1.4K提交
  • 题目提供者 Wistomize
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 搜索 枚举,暴力 队列
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    哈利•波特作为三强争霸赛的第四名选手,历尽艰险闯到了最后一关——迷宫。

    现在,迷宫里只剩下哈利和塞德里克了,哈利只有在塞德里克前面拿到奖杯,才能赢得比赛。哈利只要能看到奖杯,就可以用飞来咒拿到它,所以,现在的问题是哈利如何能尽早地看到奖杯。

    题目描述

    哈利的视力非常好,他能从迷宫的一端沿直线看到迷宫的另一端(但他只能看八个方向——东北,东,东南,南,西南……),而且跑得非常快,跑一步(向上、下、左、右移动一格)只需要1s。但迷宫是不透光的,而且,要烧掉迷宫的墙也不容易,所以哈利决定绕到一个能够看到奖杯的地方。现在,哈利希望你能帮他确定最短需要多长时间才能拿到奖杯。

    输入输出格式

    输入格式:

    第一行为2个数N,M表示迷宫的规模(N为高,M为宽)

    接下来是N*M的迷宫,O表示空地,X表示墙。

    最后是多对数据,分别是奖杯坐标及哈利的坐标(显然不可能在墙上),每对占一行,0为结束标志。

    输出格式:

    根据每对数据,计算哈利拿到奖杯的最短时间,每对一行。如果魔法部有意难为选手,用墙将奖杯包围了起来,输出”Poor Harry”。

    输入输出样例

    输入样例#1: 复制
    3 4
    OXXO
    XXOO
    XOOO
    3 2 2 4
    3 3 1 1
    0 0 0 0
    
    输出样例#1: 复制
    1
    Poor Harry
    

    说明

    对于30%的数据,有N*M<=100

    对于60%的数据,有N*M<=1600

    对于100%的数据,有N*m<=16384

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。