题目描述

宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

输入描述

第一行输入为 N，N 表示二维矩阵的大小

之后 N 行，每行有 N 个值，表格矩阵每个位置的值，其中：

• -3：妈妈
• -2：宝宝
• -1：障碍
• ≥0：糖果数（0表示没有糖果，但是可以走）

输出描述

输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

用例

输入

4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3

输出

9

说明

此地图有两条最短路径可到达宝宝位置，绿色线和黄色线都是最短路径6步，但黄色拿到的糖果更多，9个。

输入

4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3

输出

-1

说明

此地图妈妈无法到达宝宝位置

Java

import java.util.*;

// 主类
public class Main {
    // 定义四个方向移动的坐标变化（上、右、下、左）
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};

    // 主函数
    public static void main(String[] args) {
        // 使用 Scanner 读取输入数据
        Scanner scanner = new Scanner(System.in);
        // 读取矩阵的大小
        int N = scanner.nextInt();
        // 初始化矩阵
        int[][] grid = new int[N][N];
        // 初始化访问数组，记录到达每个位置的最短步数和糖果数量
        int[][][] visited = new int[N][N][2]; // [x][y][0] 代表步数，[x][y][1] 代表糖果数
        // 将访问数组初始化为 -1
        for (int[][] layer : visited) {
            for (int[] cell : layer) {
                Arrays.fill(cell, -1);
            }
        }
        // 初始化队列，用于 BFS 搜索
        Queue<Node> queue = new LinkedList<>();
        // 初始化起点
        Node start = null;

        // 读取矩阵信息，并找到起点位置
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = scanner.nex