Day 60 总结
- 自己实现中遇到哪些困难
- 今日收获，记录一下自己的学习时间
- 13:00 - 14:00
BFS
题目：127. 骑士的攻击
给定两个坐标，搜索最短路径
使用 BFS，广度搜索，按层搜索找到最短路径
public class Main {public static void main(String[] args) {new Main().solve();}public void solve() {Scanner sc = null;try {sc = new Scanner(new File("1.txt"));} catch (FileNotFoundException e) {e.printStackTrace();}int n = sc.nextInt();for (int i=0; i<n; i++) {int a1 = sc.nextInt();int a2 = sc.nextInt();int b1 = sc.nextInt();int b2 = sc.nextInt();bfs(a1,a2,b1,b2);}}public void bfs(int a1, int a2, int b1, int b2) {int[][] dir = {{-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2},};Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{a1,a2});int[][] moves = new int[1001][1001];// 1000 * 1000的棋盘while (!queue.isEmpty()) {int[] pos = queue.poll();int x = pos[0];int y = pos[1];if (x == b1 && y == b2) break;for (int i=0; i<8; i++) {int xx = x+dir[i][0];int yy = y+dir[i][1];if (xx >= 1 && xx <= 1000 && yy >= 1 && yy <= 1000 && moves[xx][yy]==0) {queue.add(new int[]{xx, yy});moves[xx][yy] = moves[x][y] + 1;}}}System.out.println(moves[b1][b2]);}
}
AStart
同样是BFS，但是有一些额外的信息
BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索
启发式函数 要影响的就是队列里元素的排序，去引导搜索方向
队列里节点进行排序，就需要给每一个节点权值
每个节点的权值为F，给出公式为：F = G + H
G：起点达到目前遍历节点的距离
H：目前遍历的节点到达终点的距离
距离计算公式
本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：
- 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
- 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
- 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))
本题，采用欧拉距离才能最大程度体现 点与点之间的距离。
所以 使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。 （路径可能不同，但路径上的节点数是相同的）
A * 算法的寻路过程，动画地址：https://kamacoder.com/tools/knight.html
通过优先级队列选择节点
@FunctionalInterface
interface Heuristic {int apply(int a1, int a2, int b1, int b2);
}public class Main {public static void main(String[] args) {new Main().solve();}public void solve() {Scanner sc = null;try {sc = new Scanner(new File("1.txt"));} catch (FileNotFoundException e) {e.printStackTrace();}int n = sc.nextInt();for (int i=0; i<n; i++) {int a1 = sc.nextInt();int a2 = sc.nextInt();int b1 = sc.nextInt();int b2 = sc.nextInt();Heuristic myHeuristic = (x1,y1,x2,y2) -> {return (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);};AStar(a1,a2,b1,b2, myHeuristic);}}public void AStar(int a1, int a2, int b1, int b2, Heuristic heuristic) {int[][] dir = {{-2,-1}, {-2,1}, {-1,2}, {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2},};PriorityQueue<int[]> queue = new PriorityQueue<int[]>((a, b) -> {return Integer.compare(a[2], b[2]);});queue.add(new int[]{a1,a2,0});int[][] moves = new int[1001][1001];// 1000 * 1000的棋盘while (!queue.isEmpty()) {int[] pos = queue.poll();int x = pos[0];int y = pos[1];int f = pos[2];if (x == b1 && y == b2) break;for (int i=0; i<8; i++) {int xx = x+dir[i][0];int yy = y+dir[i][1];if (xx >= 1 && xx <= 1000 && yy >= 1 && yy <= 1000 && moves[xx][yy]==0) {// 这里的g的计算为什么是这样子的啊？// 起点达到目前遍历节点的距离int g1 = heuristic.apply(a1, a2, xx, yy);int g = f + 5;int h = heuristic.apply(xx, yy, b1, b2);int ff = g + h;queue.add(new int[]{xx, yy, ff});moves[xx][yy] = moves[x][y] + 1;}}}System.out.println(moves[b1][b2]);}}
