当前位置：首页 > news >正文

代码随想录算法训练营第五十三天

news 2025/6/16 17:10:36

卡码网题目:

97. 小明逛公园
127. 骑士的攻击

其他:

今日总结
往期打卡

97. 小明逛公园

跳转: 97. 小明逛公园

学习: 代码随想录公开讲解

问题:

小明喜欢去公园散步，公园内布置了许多的景点，相互之间通过小路连接，小明希望在观看景点的同时，能够节省体力，走最短的路径。

给定一个公园景点图，图中有 N 个景点（编号为 1 到 N），以及 M 条双向道路连接着这些景点。每条道路上行走的距离都是已知的。

小明有 Q 个观景计划，每个计划都有一个起点 start 和一个终点 end，表示他想从景点 start 前往景点 end。由于小明希望节省体力，他想知道每个观景计划中从起点到终点的最短路径长度。请你帮助小明计算出每个观景计划的最短路径长度。

思路:

Floyd算法,适合求任意起点终点之间的最短路
以每个节点为中点将其他节点之间的距离更新一遍,就可以得到每个节点到所有节点的最短路

复杂度:

时间复杂度: $O(n^3)$
空间复杂度: $O(n^2)$

代码:

import java.util.*;public class Main {public static void main(String[] args) {int INF = 0x3f3f3f3f;Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] w = new int[n + 1][n + 1];for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)w[j][i] = w[i][j] = i == j ? 0 : INF;for(int i = 0;i < m;i++){int u = scanner.nextInt();int v = scanner.nextInt();int weight = scanner.nextInt();w[v][u] = w[u][v] = weight;}for(int p = 1;p <= n;p++){for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++)w[i][j] = Math.min(w[i][j],w[i][p] + w[p][j]);}int q = scanner.nextInt();while(q-- > 0){int start = scanner.nextInt();int end = scanner.nextInt();int len = w[start][end];System.out.println(len >= INF / 2 ? -1 : len);}}
}

127. 骑士的攻击

跳转: 127. 骑士的攻击

学习: 代码随想录公开讲解

问题:

在象棋中，马和象的移动规则分别是“马走日”和“象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

棋盘大小 1000 x 1000（棋盘的 x 和 y 坐标均在 [1, 1000] 区间内，包含边界）

思路:

A算法,BFS算法的优化,每次选择权重最大的路径继续走(dijkstra也是每次更新距离,不过其模式比较固定,依赖边权,而且不支持处理负环,A是依照启发式算法排序,比较灵活)

复杂度:

时间复杂度: $O (n l o g n)$ (取决于启发式算法,可能退化成n^2)
空间复杂度: $O(n^2)$

代码:

import java.util.*;class Main{public static int[][] dir = {{-2,-1},{-2,1},{2,1},{2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};public static int[][] moves = new int[1001][1001];public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();while(n-- > 0){int a1 = scanner.nextInt();int a2 = scanner.nextInt();int b1 = scanner.nextInt();int b2 = scanner.nextInt();System.out.println(astar(a1,a2,b1,b2));}}private static int astar(int a1, int a2, int b1, int b2) {PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return Integer.compare(o1[4],o2[4]);}});for(int[] i : moves)Arrays.fill(i,-1);moves[a1][a2] = 0;int h = heuristic(a1,a2,b1,b2);pq.offer(new int[]{a1,a2,0,h,h});while(!pq.isEmpty()){int[] cur = pq.poll();if(cur[0] == b1 && cur[1] == b2){return moves[b1][b2];}for(int[] i : dir){int nx = cur[0] + i[0];int ny = cur[1] + i[1];if(nx >= 1 && nx <= 1000 && ny >= 1 && ny <= 1000 && moves[nx][ny] == -1){moves[nx][ny] = moves[cur[0]][cur[1]] + 1;int h1 = heuristic(nx,ny,b1,b2);int g1 = cur[2] + 5;pq.offer(new int[]{nx,ny,g1,h1,h1 + g1});}}}return -1;}private static int heuristic(int a1, int a2, int b1, int b2) {// return Math.abs((a1 + a2) - (b1 + b2));return (int) (Math.pow(a1 - b1,2) + Math.pow(a2 - b2,2));}
}