TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1201
  • 题目
  • P1201Pugna大战何老板3.0
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    尽管现在pudge有很多蓝,但是何老板发现他始终不能用钩子钩到人!眼看着Pugna三路推进,已经快上高地了,机智的何老板想到了一个好主意。
    就是现在!何老板看到Pugna没有在线上了,他也知道Pugna是去野外的商店合装备。机智的何老板马上打开了教师机,对Pugna的机子进行了“请您肃静”,效果非常明显,Pugna只能站在那里不能动了。然后何老板很快地打开了一个小软件,看到了全图。现在,他准备用钩子把Pugna拉到自己身边然后慢慢A掉。
    我们假设野区的地图就是一个N×N的正方形矩阵。其中0代表空地,1代表树(障碍物)。当然何老板还发现了对方在野区插了一个眼,眼的视力范围为上下左右各1格,何老板不想被对方的人看到,也就是说他不能走到这个眼的视力范围里面(我们假设这个眼只能在空地上并且永久在那里)。当然,不要忘了Pudge的技能,肉钩。就是放一个钩子,这个钩子只能沿着一条直线向前移动,无视树木。如果钩子碰到了玩家就会把这个玩家钩到自己身边。现在我们假设整个野区只有Pugna,Pudge和眼。Pudge的钩子没有距离限制,但是只能沿着上下左右四个正方向和两条斜对角线移动。Pudge每秒可以向上下左右四个方向移动一格。钩子的速度也是每秒一格。何老板想知道怎样才能尽快到达Pugna那里。(简单的说,就是走到Pugna站的那个格子或者走到另外一个格子然后在那个格子用钩子钩到Pugna)。如果不能在不被眼发现的情况下走到Pugna那里,则输出-1(输入数据保证Pudge起始的位置不会在眼的视野范围内)。

    输入格式

    第一行,一个整数N(N<=15)
    接下来是一个N*N的矩阵,每个数用空格隔开。0表示空地,1表示树木,2表示Pudge,5表示Pugna,4表示眼。

    输出格式

    一个整数t,表示最短时间。

    样例输入

    样例输入1:
    8
    1 1 1 0 0 0 1 0
    0 0 0 0 1 0 0 0
    0 0 0 0 1 5 0 0
    1 1 0 0 1 1 1 1
    1 0 0 0 4 0 0 0
    0 0 0 1 1 0 0 0
    2 0 1 1 1 1 0 0
    0 1 1 1 1 1 0 0
    样例输入2:
    5
    0 0 0 5 0
    0 1 0 1 0
    4 0 1 0 1
    0 0 0 1 0
    2 0 1 1 1

    样例输出

    样例输出1:
    5
    样例输出2:
    -1

    提示


    样例说明:
    1:先向右走一步,然后斜着钩。在第五秒的时候钩子碰到Pugna。
    2:无论怎么走都不能钩到,因为能钩到的两个位置都在眼旁边。


    来源  有问题找铺盖