P2802 回家
时间限制
1.00s
内存限制
125.00MB
题目描述
小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,否则输出他回家所需最短时间。
输入输出样例
输入
3 3
2 1 1
1 1 0
1 1 3
输出
4
说明/提示
1<=n,m<=9
package com.company;
import java.util.Scanner;
public class 回家 {
private static int n;
private static int m;
private static void dfs(int x, int y, int[][] f, int hp) {
// 边界判断
if (x < 0 || y < 0 || x == n || y == m || hp == 0 || f[x][y] == 0 || flag[x][y]>3) return;
if (time < num) return; // 剪枝
if (f[x][y] == 3) { // 到达出口
if (time > num) {
time = num;
}
return;
}
if (f[x][y] == 4) {
hp = 6;
}
flag[x][y] ++;
num++;
dfs(x + 1, y, f, hp - 1);
dfs(x, y - 1, f, hp - 1);
dfs(x - 1, y, f, hp - 1);
dfs(x, y + 1, f, hp - 1);
flag[x][y] --;
num--;
}
private static int time = Integer.MAX_VALUE;
private static int num = 0;
private static int [][] flag;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
flag = new int[n][m];
sc.nextLine();
int[][] f = new int[n][m];
int x = 0, y = 0;
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[0].length; j++) {
f[i][j] = sc.nextInt();
if (f[i][j] == 2) {
x = i;
y = j;
}
}
}
dfs(x, y, f, 6);
if (time == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(time);
}
}