P2802 回家

    • 1.4K通过
    • 7.3K提交
  • 题目提供者 飞翔
  • 评测方式 云端评测
  • 标签 剪枝 搜索 深度优先搜索,DFS
  • 难度 普及-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小H在一个划分成了n*m个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小H不可以静止不动), 但不能离开封锁线,否则就被打死了。 刚开始时他有满血6点,每移动一格他要消耗1点血量。一旦小H的 血量降到 0, 他将死去。 他可以沿路通过拾取鼠标(什么鬼。。。)来补满血量。只要他走到有鼠标的格子,他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满,所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才死去, 他也不能通过拾取鼠标补满 HP。 即使在家门口死去, 他也不能算完成任务回到家中。

    地图上有 5 种格子:

    数字 0: 障碍物。

    数字 1: 空地, 小H可以自由行走。

    数字 2: 小H出发点, 也是一片空地。

    数字 3: 小H的家。

    数字 4: 有鼠标在上面的空地。

    小H能否安全回家?如果能, 最短需要多长时间呢?

    输入输出格式

    输入格式:

    第一行两个整数n,m, 表示地图的大小为n*m。

    下面 n 行, 每行 m 个数字来描述地图。

    输出格式:

    一行, 若小H不能回家, 输出-1,否则输出他回家所需最短时间。

    输入输出样例

    输入样例#1: 复制
    3 3
    2 1 1
    1 1 0
    1 1 3
    输出样例#1: 复制
    4

    说明

    1<=n,m<=9

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