华为5.7机考-最小代价相遇的路径规划Java题解

题目内容

输入描述

输出描述

示例：

输入：

2
1 2
2 1

输出：

3

思路：

Dijkstra 算法实现

dijkstra(int sx, int sy, int[][] dirs) 方法：

• 参数：起点坐标 (sx, sy) 和允许的移动方向

• 初始化：

  • dist 数组存储到每个点的最短距离，初始为 INF

  • 起点的距离初始化为该点的值 grid[sx][sy]

• 优先队列：存储待处理的节点，按距离从小到大排序

• 处理队列：

  • 取出当前距离最小的点

  • 跳过已经处理过的点（距离大于当前存储的距离）

  • 检查所有允许方向的邻居

  • 如果找到更短路径，更新距离并加入队列

主逻辑

• 从起点 (0,0) 和终点 (n-1,n-1) 分别执行 Dijkstra 算法

  • dirs1: 只允许向右和向下移动

  • dirs2: 只允许向左和向上移动

• 遍历所有可能的中间点：

  • 检查当前点是否可达（距离不为 INF）

  • 检查四个方向的邻居是否可达

  • 计算路径的最大值（从起点到当前点，和从邻居到终点的最大值）

  • 更新全局最小值 ans

1. Dijkstra 算法的变种：

   • 传统 Dijkstra 用于图的最短路径，这里应用于网格

   • 允许的移动方向由参数控制，可以灵活调整

2. 双向搜索思想：

   • 从起点和终点分别搜索，提高效率

   • 在中间点汇合时计算最终结果

3. 优先队列的使用：

   • Java 的 PriorityQueue 默认是最小堆

   • 通过 Comparator.comparingLong(a -> a[0]) 确保按距离排序

4. 边界条件处理：

   • 检查坐标是否越界

   • 跳过值为 0 的障碍点

   • 处理不可达情况（距离为 INF）

import java.util.*;
import java.io.*;

public class GridShortestPath {
    static final long INF = (long)1e18;
    static int n;
    static int[][] grid;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        
        // 读取网格数据
        for (int i = 0; i < n; i++) {
            String[] row = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(row[j]);
            }
        }
        
        // 定义两个方向的移动
        int[][] dirs1 = {{0, 1}, {1, 0}};  // 向右和向下
        int[][] dirs2 = {{-1, 0}, {0, -1}}; // 向左和向上
        
        // 从起点(0,0)开始计算最短路径
        long[][] dist1 = dijkstra(0, 0, dirs1);
        // 从终点(n-1,n-1)开始计算最短路径
        long[][] dist2 = dijkstra(n-1, n-1, dirs2);
        
        long ans = INF;
        // 遍历所有可能的中间点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 || dist1[i][j] == INF) continue;
                
                // 检查四个方向的邻居
                int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                for (int[] dir : directions) {
                    int ni = i + dir[0];
                    int nj = j + dir[1];
                    
                    if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
                    if (grid[ni][nj] == 0 || dist2[ni][nj] == INF) continue;
                    
                    // 计算当前路径的最大值
                    long currentMax = Math.max(dist1[i][j], dist2[ni][nj]);
                    ans = Math.min(ans, currentMax);
                }
            }
        }
        
        System.out.println(ans == INF ? -1 : ans);
    }
    
    // Dijkstra算法实现
    static long[][] dijkstra(int sx, int sy, int[][] dirs) {
        long[][] dist = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i], INF);
        }
        dist[sx][sy] = grid[sx][sy];
        
        // 优先队列，按距离排序
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.add(new long[]{dist[sx][sy], sx, sy});
        
        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long d = current[0];
            int x = (int)current[1];
            int y = (int)current[2];
            
            if (d > dist[x][y]) continue;
            
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (grid[nx][ny] == 0) continue;
                
                long nd = d + grid[nx][ny];
                if (nd < dist[nx][ny]) {
                    dist[nx][ny] = nd;
                    pq.add(new long[]{nd, nx, ny});
                }
            }
        }
        
        return dist;
    }
}