Java实现洛谷 P2802 回家

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);

    }

}

巴特西

Java实现洛谷 P2802 回家

P2802 回家

最新文章

热门文章