码随想录算法训练营第62天|卡码网：97. 小明逛公园、127. 骑士的攻击

1. 卡码网 97. 小明逛公园

题目链接：https://kamacoder.com/problempage.php?pid=1155
文章链接：https://www.programmercarl.com/kamacoder/0097.小明逛公园.html

思路：
使用Floyd 算法，目的是解决多源最短路问题，即 求多个起点到多个终点的多条最短路径。
动规五部曲：
1、确定dp数组（dp table）以及下标的含义
用 grid数组来存图，那就把dp数组命名为 grid。
grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。
注意：[1…k] ，表示节点1 到 节点k 一共k个节点的集合。
2、确定递推公式
分两种情况：
1.节点i 到 节点j 的最短路径经过节点k
对于该情况，grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点k 的最短距离 是不经过节点k，中间节点集合为[1…k-1]，所以 表示为grid[i][k][k - 1]
节点k 到 节点j 的最短距离 也是不经过节点k，中间节点集合为[1…k-1]，所以表示为 grid[k][j][k - 1]
2.节点i 到 节点j 的最短路径不经过节点k
对于该情况，grid[i][j][k] = grid[i][j][k - 1]
如果节点i 到 节点j的最短距离 不经过节点k，那么 中间节点集合[1…k-1]，表示为 grid[i][j][k - 1]
因为我们是求最短路，对于这两种情况自然是取最小值。
即： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])
3.dp数组如何初始化

vector<vector<vector<int>>> grid(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1, 10005)));  // C++定义了一个三位数组，10005是因为边的最大距离是10^4

for(int i = 0; i < m; i++){
    cin >> p1 >> p2 >> val;
    grid[p1][p2][0] = val;
    grid[p2][p1][0] = val; // 注意这里是双向图
} 

注意：输入数据没有涉及到的节点的情况都应该初始为一个最大数，此处设值为10005。
4.确定遍历顺序
初始化时，我们是把 k =0 的 i 和j 对应的数值都初始化了，这样才能去计算 k = 1 的时候 i 和 j 对应的数值。
因此，遍历k 的for循环一定是在最外面，遍历 i 和 j 的话，for 循环的先后顺序无所谓。

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1]);
        }
    }
}

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 景点的数量
        int m = sc.nextInt(); // 道路的数量
        
        // 1. 定义dp数组和下标
        // dp[i][j][k] 表示节点i 到 节点j 以[1...k] 集合为中间节点的最短距离。
        int[][][] dp = new int[n+1][n+1][n+1];
        // 2. 递推公式
        // dp[i][j][k] = Math.min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1]);
        // 3. 初始化
        for (int i=0;i<=n;i++) {
            for (int j=0;j<=n;j++) {
                Arrays.fill(dp[i][j],10005);
            }
        }
        
        for (int i=0;i<m;i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            dp[u][v][0] = w;
            dp[v][u][0] = w;
        }
        
        //4. 遍历顺序
        for (int k=1;k<=n;k++) {
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    dp[i][j][k] = Math.min(dp[i][j][k-1],dp[i][k][k-1]+dp[k][j][k-1]);
                }
            }
        }
        
        int q = sc.nextInt();
        for (int i=0;i<q;i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            if (dp[start][end][n] == 10005) {
                System.out.println(-1);
            } else {
                System.out.println(dp[start][end][n]);
            }
        }
    }
}

2. 卡码网 127. 骑士的攻击

题目链接：https://kamacoder.com/problempage.php?pid=1203
文章链接：https://www.programmercarl.com/kamacoder/0126.骑士的攻击astar.html

思路：
使用Astar算法， 关键在于 启发式函数， 也就是 影响 广搜或者 dijkstra 从 容器（队列）里取元素的优先顺序。

启发式函数 要影响的就是队列里元素的排序！
对队列里节点进行排序，就需要给每一个节点权值，如何计算权值呢？
每个节点的权值为F，给出公式为：F = G + H
1.G：起点达到目前遍历节点的距离
2.H：目前遍历的节点到达终点的距离
当前遍历节点的权值F：起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离，就是起点到达终点的距离。
本题，采用欧拉距离才能最大程度体现 点与点之间的距离。
计算出来 F 之后，按照 F 的 大小，来选出队列中F最小的节点。

import java.util.*;

public class Main {
    static int[][] moves = new int[1001][1001];
    static int[][] dir = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
    static int b1, b2;

    static class Knight {
        int x, y;
        int g, h, f;

        public Knight(int x, int y, int g, int h, int f) {
            this.x = x;
            this.y = y;
            this.g = g;
            this.h = h;
            this.f = f;
        }
    }

    static class KnightComparator implements Comparator<Knight> {
        public int compare(Knight k1, Knight k2) {
            return k1.f - k2.f; // Java的优先队列默认是最小堆，所以这里用k1.f - k2.f来使得f值小的排在前面
        }
    }

    static PriorityQueue<Knight> que = new PriorityQueue<>(new KnightComparator());

    static int Heuristic(Knight k) { // 欧拉距离
        return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
    }

    static void astar(Knight k) {
        Knight cur, next;
        que.add(k);
        while (!que.isEmpty()) {
            cur = que.poll(); // 选出队列中F最小的节点
            if (cur.x == b1 && cur.y == b2) {
                break;
            }
            for (int i = 0; i < 8; i++) {
                next = new Knight(cur.x + dir[i][0], cur.y + dir[i][1], cur.g, 0, 0);
                if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) {
                    continue;
                }
                if (moves[next.x][next.y] == 0) {
                    moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
                    next.g = cur.g + 5;
                    next.h = Heuristic(next);
                    next.f = next.g + next.h;
                    que.add(next);
                }
            }
        }
    }

    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();
            b1 = scanner.nextInt();
            b2 = scanner.nextInt();
            for (int[] row : moves) {
                Arrays.fill(row, 0);
            }
            Knight start = new Knight(a1, a2, 0, Heuristic(new Knight(a1, a2, 0, 0, 0)), 0);
            start.f = start.g + start.h;
            astar(start);
            System.out.println(moves[b1][b2]);
            que.clear(); // 清空队列
        }
        scanner.close();
    }
}