回 帖 发 新 帖 刷新版面

主题:最后的迷宫

【问题描叙】
哈利•波特作为三强争霸赛的第四名选手,历尽艰险闯到了最后一关——迷宫。
现在,迷宫里只剩下哈利和塞德里克了,哈利只有在塞德里克前面拿到奖杯,才能赢得比赛。哈利只要能看到奖杯,就可以用飞来咒拿到它,所以,现在的问题是哈利如何能尽早地看到奖杯。
哈利的视力非常好,他能从迷宫的一端沿直线看到迷宫的另一端(但他只能看八个方向——东北,东,东南,南,西南……),而且跑得非常快,跑一步(向上、下、左、右移动一格)只需要1s。但迷宫是不透光的,而且,要烧掉迷宫的墙也不容易,所以哈利决定绕到一个能够看到奖杯的地方。现在,哈利希望你能帮他确定最短需要多长时间才能拿到奖杯。
【输入格式】
输入文件harry.in第一行为2个数N,M表示迷宫的规模(N为高,M为宽)
接下来是N*M的迷宫,O表示空地,X表示墙。
最后是多对数据,分别是奖杯坐标及哈利的坐标(显然不可能在墙上),每对占一行,0为结束标志。
【输出格式】
根据每对数据,计算哈利拿到奖杯的最短时间,每对一行输出到harry.out。如果魔法部有意难为选手,用墙将奖杯包围了起来,输出”Poor Harry”。
【输入样例】
3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0
【输出样例】
1
Poor Harry
数据规模
对于30%的数据,有N*M<=100
对于60%的数据,有N*M<=1600
对于100%的数据,有N*m<=16384

回复列表 (共2个回复)

沙发

先把奖杯所在的行、列、斜行都标记成目标为止,然后就和普通的解迷宫一样,找到最短距离即可。

板凳

计算完后要记得忽略最后的一条直线:)

我来回复

您尚未登录,请登录后再回复。点此登录或注册