代码随想录打卡Day66

今天是代码随想录训练营的最后一天！！！！终于坚持下来了！！！太激动了！！！！已经开始期待开营前说的奖励是啥了啊哈哈哈哈😄
今天一共有两道题，第一道就是动态规划的思想，看完以后代码就写出来了。第二道还是比较困难的，我看了很久才慢慢领略其中的思想和精髓，第二道题的代码主要还是参考代码随想录的题解代码，但是加了很多自己的注释。

97. 小明逛公园（卡码网）

这道题用的是Floyd算法，但是本质上还是动态规划的思路，这道题最难的在于dp数组的构造和dp数组的初始化，这道题dp数组的定义为：中间经过节点(不含起点和终点)在[1, 2, …, k]集合里的情况下，从i节点到j节点的最短距离（集合中的元素不一定要全部用上）为dp[i][j][k]，而初始化也比较难想，在循环中接收i节点到j节点之间的距离，但是中间经过了多少个节点我们是不知道的，我们只知道中间在不经过任何节点的情况下，从i节点到j节点之间的距离为输入的w（注意，这个距离未必是最短距离，在后续的动态规划中最短距离可能还比w小），因此我们只能在初始化的时候令k = 0，此时对应着中间不经过任何节点的情况下，从i节点走到j节点时走的最短距离，从dp数组的含义来讲，也是站得住脚的。在接收输入的时候，由于路径是双向的，所以dp[i][j][0]和dp[j][i][0]都要赋值为w。另外就是遍历顺序，一定要让k的遍历在最外层，因为从递推公式来看，dp数组的推导依赖于k - 1状态下的值，具体原因还是去看代码随想录网站上的解释吧。

#include<iostream>
#include<vector>
#include<climits>using namespace std;int main(){//1.确定dp[i][j][k]的含义：中间经过节点(不含起点和终点)在[1, 2, ..., k]中的情况下，//从i节点到j节点的最短距离（集合中的元素不一定要全部用上）//2.确定递推公式dp[i][j][k] = dp[i][k][k - 1] + dp[k][j][k - 1];  (经过节点k的情况)//              dp[i][j][k] = dp[i][j][k - 1]; (不经过节点k的情况)//              dp[i][j][k] = min(dp[i][k][k - 1] + dp[k][j][k - 1], dp[i][j][k - 1]);//3.dp数组初始化 dp[i][j][0] = w;//               dp[j][i][0] = w;//4.确定遍历顺序：i,j遍历顺序无所谓，但是k从小到大遍历，且k必须是最外层循环//5.打印数组(省略)int N, M;  //N个景点，M条道路cin >> N >> M;vector<vector<vector<int>>> dp(N + 1, vector<vector<int>> (N + 1, vector<int> (N + 1, 20000)));for(int i = 1; i <= M; i++){int u, v, w;cin >> u >> v >> w;dp[u][v][0] = w;dp[v][u][0] = w;}//开始dpfor(int k = 1; k <= N; k++){for(int i = 1; i <= N; i++){for(int j = 1; j <= N; j++)dp[i][j][k] = min(dp[i][k][k - 1] + dp[k][j][k - 1], dp[i][j][k - 1]);}}int Q;  //观景计划的数量cin >> Q;for(int i = 0; i < Q; i++){int start, end;cin >> start >> end;if(dp[start][end][N] >= 20000) cout << -1 << endl;else cout << dp[start][end][N] << endl;}return 0;
}

127. 骑士的攻击

这道题用的A算法以前是从来都没听过，理解起来相当费劲，但是好在主要思想还是看懂了，对于一个骑士而言，他总共有8个移动方向，从最小化路径的角度来说，这8个移动方向一定是有优先级顺序的，而这些方向哪些需要重点去探索，哪些则可以搁置在一边，主要还是看这些方向的权重，而权重的大小就量化为骑士从起点走到下一步的位置的欧氏距离与下一步的位置到终点之间的欧氏距离之和，如果权重越小，则这个方向是更有可能接近终点的方向，在遍历中应当优先考虑，这8个方向都应该压入队列中，但是需要队列对这些方向进行自动排序，然后自动弹出优先级最高的方向，这样就能够更高效的遍历。注意，在主函数中有多个骑士坐标和终点坐标输入，所以应该定义一个循环，每一次循环都是对不同的骑士，不同的终点进行A算法的计算，因此在每一次计算前，记得要先将地图初始化为0，及时把上一次循环留下的痕迹抹去。

#include<iostream>
#include<queue>
#include<cstring>using namespace std;// 定义骑士结构体
typedef struct Knight{int x, y;   //骑士当前的坐标// F = G + H// G = 从起点到该节点路径消耗// H = 该节点到终点的预估消耗// F为节点的权值int g, h, f;bool operator < (const Knight& k) const { //重载比较运算符，权值大的排下面return k.f < f;}}Knight;int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};   //8个移动方向
int b1, b2;  //终点坐标
int moves[1001][1001];  //整个地图priority_queue<Knight> que;  //存放骑士的优先级队列int Heuristic(const Knight& k);
void astar(const Knight& k);int main(){int n;cin >> n;while(n > 0){int a1, a2;cin >> a1 >> a2 >> b1 >> b2;memset(moves,0,sizeof(moves));  //每次循环及时将地图清零，清除上一个骑士的计算结果Knight start;start.x = a1;start.y = a2;start.g = 0;start.h = Heuristic(start);start.f = start.g + start.h;astar(start);//及时清空队列while(!que.empty())que.pop();cout << moves[b1][b2] << endl;n--;}return 0;
}int Heuristic(const Knight& k) { // 欧拉距离//计算骑士与终点之间的欧拉距离的平方return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 统一不开根号，这样可以提高精度
}void astar(const Knight& k)
{Knight cur, next;que.push(k);while(!que.empty()){cur = que.top(); que.pop();if(cur.x == b1 && cur.y == b2)  //已经走到终点break;for(int i = 0; i < 8; i++)  //遍历8个方向的落脚点{next.x = cur.x + dir[i][0];next.y = cur.y + dir[i][1];if(next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) //越界访问continue;if(!moves[next.x][next.y])  //确保下一个落脚点不在{//赋值为非零值，防止重复访问，且便于结果统计到底走了几步moves[next.x][next.y] = moves[cur.x][cur.y] + 1;  // 开始计算Fnext.g = cur.g + 5; // 统一不开根号，这样可以提高精度，马走日，1 * 1 + 2 * 2 = 5next.h = Heuristic(next);next.f = next.g + next.h;que.push(next);}}}
}