亲子游戏

 宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。
 游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。
 请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。
 输入描述：第一行输入为N（N <= 50），N标识二维矩阵的大小 之后N行，每行有N个值，表格矩阵每个位置的值
 其中：
  -3：妈妈
  -2：宝宝
  -1：障碍
  >=0：糖果数(0表示没有糖果，但是可以走)
 输出描述：输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

完成大部分的简单实现

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nn = new int[n][n];
        int[][] dp = new int[n][n]; // 记录到达每个位置的最大和
        boolean[][] visited = new boolean[n][n]; // 记录是否访问过
        
        // 初始化dp为最小值
        for(int i = 0; i < n; i++){
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int m = sc.nextInt();
                nn[i][j] = m;
                if(m == -3){
                    // 起点，和为0
                    dp[i][j] = 0;
                    visited[i][j] = true;
                    queue.offer(i * n + j);
                }
            }
        }
        
        int total = -1;
        boolean found = false;
        
        while(!queue.isEmpty() && !found){
            int size = queue.size();
            
            for(int i = 0; i < size && !found; i++){
                int index = queue.poll();
                int row = index / n;
                int col = index % n;
                int currentSum = dp[row][col];
                
                // 上
                if(row - 1 >= 0 && nn[row - 1][col] != -1 && !visited[row - 1][col]){
                    int newSum = currentSum;
                    if(nn[row - 1][col] != -2){
                        newSum += Math.max(0, nn[row - 1][col]); // 只加非负值
                    }
                    
                    if(nn[row - 1][col] == -2){
                        total = Math.max(total, newSum);
                        found = true;
                    } else {
                        dp[row - 1][col] = newSum;
                        visited[row - 1][col] = true;
                        queue.offer((row - 1) * n + col);
                    }
                }
                
                // 下
                if(row + 1 < n && nn[row + 1][col] != -1 && !visited[row + 1][col]){
                    int newSum = currentSum;
                    if(nn[row + 1][col] != -2){
                        newSum += Math.max(0, nn[row + 1][col]);
                    }
                    
                    if(nn[row + 1][col] == -2){
                        total = Math.max(total, newSum);
                        found = true;
                    } else {
                        dp[row + 1][col] = newSum;
                        visited[row + 1][col] = true;
                        queue.offer((row + 1) * n + col);
                    }
                }
                
                // 左
                if(col - 1 >= 0 && nn[row][col - 1] != -1 && !visited[row][col - 1]){
                    int newSum = currentSum;
                    if(nn[row][col - 1] != -2){
                        newSum += Math.max(0, nn[row][col - 1]);
                    }
                    
                    if(nn[row][col - 1] == -2){
                        total = Math.max(total, newSum);
                        found = true;
                    } else {
                        dp[row][col - 1] = newSum;
                        visited[row][col - 1] = true;
                        queue.offer(row * n + col - 1);
                    }
                }
                
                // 右
                if(col + 1 < n && nn[row][col + 1] != -1 && !visited[row][col + 1]){
                    int newSum = currentSum;
                    if(nn[row][col + 1] != -2){
                        newSum += Math.max(0, nn[row][col + 1]);
                    }
                    
                    if(nn[row][col + 1] == -2){
                        total = Math.max(total, newSum);
                        found = true;
                    } else {
                        dp[row][col + 1] = newSum;
                        visited[row][col + 1] = true;
                        queue.offer(row * n + col + 1);
                    }
                }
            }
        }
        
        System.out.print(total);
    }
}

完全实现

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nn = new int[n][n];
        
        // 记录到达每个位置的最大和
        int[][] maxSum = new int[n][n];
        // 记录到达每个位置的最短距离
        int[][] dist = new int[n][n];
        
        // 初始化数组
        for(int i = 0; i < n; i++){
            Arrays.fill(maxSum[i], Integer.MIN_VALUE);
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        int startX = -1, startY = -1;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                nn[i][j] = sc.nextInt();
                if(nn[i][j] == -3){
                    startX = i;
                    startY = j;
                    // 初始化起点的距离和和值
                    maxSum[i][j] = 0;
                    dist[i][j] = 0;
                    queue.offer(i * n + j);
                }
            }
        }
        
        // 将total改为-1，minDist记录最短距离
        int total = -1;
        int minDist = Integer.MAX_VALUE; // 记录找到的最短距离
        
        while(!queue.isEmpty()){
            int index = queue.poll();
            int row = index / n;
            int col = index % n;
            int currentDist = dist[row][col]; // 当前距离
            int currentSum = maxSum[row][col]; //当前和值
            
            // 如果当前距离已经大于已知的最短距离，跳过
            if(currentDist > minDist) continue;
            
            // 上
            if(row - 1 >= 0 && nn[row - 1][col] != -1){
                int newRow = row - 1;
                int newCol = col;
                int newDist = currentDist + 1; // 使用当前距离计算新距离
                int newSum = currentSum; // 使用当前和值计算新和值
                
                if(nn[newRow][newCol] != -2){
                    newSum += Math.max(0, nn[newRow][newCol]);
                }
                
                if(nn[newRow][newCol] == -2){
                    // 处理终点逻辑，考虑多条最短路径
                    if(newDist < minDist){
                        minDist = newDist;
                        total = newSum;
                    } else if(newDist == minDist){
                        total = Math.max(total, newSum);
                    }
                    continue;
                }
                
                // 更新普通格子的逻辑
                if(newDist < dist[newRow][newCol]){
                    // 找到更短路径，更新距离和和值
                    dist[newRow][newCol] = newDist;
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                } else if(newDist == dist[newRow][newCol] && newSum > maxSum[newRow][newCol]){
                    // 相同距离但和值更大，更新和值
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                }
            }
            
            // 下
            if(row + 1 < n && nn[row + 1][col] != -1){
                int newRow = row + 1;
                int newCol = col;
                int newDist = currentDist + 1;
                int newSum = currentSum;
                
                if(nn[newRow][newCol] != -2){
                    newSum += Math.max(0, nn[newRow][newCol]);
                }
                
                if(nn[newRow][newCol] == -2){
                    if(newDist < minDist){
                        minDist = newDist;
                        total = newSum;
                    } else if(newDist == minDist){
                        total = Math.max(total, newSum);
                    }
                    continue;
                }
                
                if(newDist < dist[newRow][newCol]){
                    dist[newRow][newCol] = newDist;
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                } else if(newDist == dist[newRow][newCol] && newSum > maxSum[newRow][newCol]){
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                }
            }
            
            // 左
            if(col - 1 >= 0 && nn[row][col - 1] != -1){
                int newRow = row;
                int newCol = col - 1;
                int newDist = currentDist + 1;
                int newSum = currentSum;
                
                if(nn[newRow][newCol] != -2){
                    newSum += Math.max(0, nn[newRow][newCol]);
                }
                
                if(nn[newRow][newCol] == -2){
                    if(newDist < minDist){
                        minDist = newDist;
                        total = newSum;
                    } else if(newDist == minDist){
                        total = Math.max(total, newSum);
                    }
                    continue;
                }
                
                if(newDist < dist[newRow][newCol]){
                    dist[newRow][newCol] = newDist;
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                } else if(newDist == dist[newRow][newCol] && newSum > maxSum[newRow][newCol]){
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                }
            }
            
            // 右
            if(col + 1 < n && nn[row][col + 1] != -1){
                int newRow = row;
                int newCol = col + 1;
                int newDist = currentDist + 1;
                int newSum = currentSum;
                
                if(nn[newRow][newCol] != -2){
                    newSum += Math.max(0, nn[newRow][newCol]);
                }
                
                if(nn[newRow][newCol] == -2){
                    if(newDist < minDist){
                        minDist = newDist;
                        total = newSum;
                    } else if(newDist == minDist){
                        total = Math.max(total, newSum);
                    }
                    continue;
                }
                
                if(newDist < dist[newRow][newCol]){
                    dist[newRow][newCol] = newDist;
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                } else if(newDist == dist[newRow][newCol] && newSum > maxSum[newRow][newCol]){
                    maxSum[newRow][newCol] = newSum;
                    queue.offer(newRow * n + newCol);
                }
            }
        }
        
        System.out.print(total == -1 ? -1 : total);
    }
}