混境之地1

问题描述

小蓝有一天误入了一个混境之地。

好消息是：他误打误撞拿到了一张地图，并从中获取到以下信息：

1. 混境之地的大小为 n⋅mn⋅m，其中 # 表示这个位置很危险，无法通行，. 表示道路，可以通行。
2. 他现在所在位置的坐标为 (A,B)(A,B) ，而这个混境之地出口的坐标为 (C,D)(C,D) ，当站在出口时即表示可以逃离混境之地。
3. 混境之地中有 kk 个单向传送门，当你站在上面时，你可以选择消耗 pipi​ 点能量，从当前点 (x1i,y1i)(x1i​,y1i​) 传送至 (x2i,y2i)(x2i​,y2i​) ，同样你也可以选择不通过该传送门。

坏消息是：小蓝仅剩下 EE 点能量。

小蓝可以往上下左右四个方向行走，每行走一步，消耗一点能量。

小蓝想知道他能否逃离这个混境之地，如果可以逃离这里，请你帮他计算一下，他最多可以剩下多少能量，如果无法逃离则输出 -1 。

输入格式

第 11 行输入两个正整数 n,mn,m ，表示混境之地的大小。

第 22 行输入四个正整数 A,B,C,DA,B,C,D ，表示小蓝当前所在位置的坐标，以及混境之地出口的坐标。

第 33 行至第 n+2n+2 行，每行 mm 个字符，表示混境之地的地图，其中 # 表示为危险的地方， . 表示普通的道路。

第 n+3n+3 行输入一个正整数 kk ，表示传送门的数量。

接下来 kk 行，每行五个正整数 x1i,y1i,x2i,y2i,pix1i​,y1i​,x2i​,y2i​,pi​ ，表示 (x1i,y1i)(x1i​,y1i​) 处有一个单项传送门，可以消耗 pipi​ 点能量使用该传送门从 (x1i,y1i)(x1i​,y1i​) 传送至 (x2i,y2i)(x2i​,y2i​) 。

最后一行输入一个 EE ，表示小蓝剩下的能量值。

输出格式

输出数据共一行为一个整数：

• 若小蓝可以逃离混境之地，则输出他最多可以剩下的能量值。
• 若小蓝无法逃离混境之地，则输出 -1 。

样例输入1

5 5
1 1 2 5
...#.
..#..
#...#
...#.
.....
2
1 2 5 3 1
1 3 1 5 2
7

样例输出1

2

import java.util.*;public class Main {// 定义方向数组（上下左右）private static final int[][] DIRECTIONS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入地图大小int n = scanner.nextInt();int m = scanner.nextInt();// 输入起点和终点坐标 (转换为0索引)int A = scanner.nextInt() - 1;int B = scanner.nextInt() - 1;int C = scanner.nextInt() - 1;int D = scanner.nextInt() - 1;// 输入地图char[][] grid = new char[n][m];for (int i = 0; i < n; i++) {String line = scanner.next();grid[i] = line.toCharArray();}// 输入传送门数量int k = scanner.nextInt();// 构建传送门字典Map<String, List<int[]>> portals = new HashMap<>();for (int i = 0; i < k; i++) {int x1 = scanner.nextInt() - 1;int y1 = scanner.nextInt() - 1;int x2 = scanner.nextInt() - 1;int y2 = scanner.nextInt() - 1;int p = scanner.nextInt();String key = x1 + "," + y1;if (!portals.containsKey(key)) {portals.put(key, new ArrayList<>());}portals.get(key).add(new int[]{x2, y2, p});}// 输入初始能量int E = scanner.nextInt();// 初始化优先队列，存储 (-e, x, y)，按剩余能量从大到小排序PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> -a[0]));pq.offer(new int[]{E, A, B});// 访问标记数组，记录每个位置的最大剩余能量int[][] visited = new int[n][m];for (int[] row : visited) {Arrays.fill(row, -1);}visited[A][B] = E;// 开始搜索while (!pq.isEmpty()) {int[] currentState = pq.poll();int remainingEnergy = currentState[0];int x = currentState[1];int y = currentState[2];// 如果到达终点，输出剩余能量if (x == C && y == D) {System.out.println(remainingEnergy);return;}// 尝试上下左右移动for (int[] dir : DIRECTIONS) {int nx = x + dir[0];int ny = y + dir[1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.') {int newEnergy = remainingEnergy - 1;if (newEnergy > visited[nx][ny]) {visited[nx][ny] = newEnergy;pq.offer(new int[]{newEnergy, nx, ny});}}}// 尝试使用传送门String key = x + "," + y;if (portals.containsKey(key)) {for (int[] portal : portals.get(key)) {int tx = portal[0];int ty = portal[1];int cost = portal[2];if (remainingEnergy >= cost) {int newEnergy = remainingEnergy - cost;if (newEnergy > visited[tx][ty]) {visited[tx][ty] = newEnergy;pq.offer(new int[]{newEnergy, tx, ty});}}}}}// 如果无法到达终点，输出 -1System.out.println(-1);}
}