企业官网建设流程全解析

网站建设案例的公司,个体户做网站去哪里做,wordpress 入侵视频教程,wordpress加入链接【题目描述】 在各种棋中#xff0c;棋子的走法总是一定的#xff0c;如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性#xff0c;因此#xff0c;他规定马既能按“日”走#xff0c;也能如象一样走“田”字。他的同桌平时喜欢下围棋#xff…【题目描述】在各种棋中棋子的走法总是一定的如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性因此他规定马既能按“日”走也能如象一样走“田”字。他的同桌平时喜欢下围棋知道这件事后觉得很有趣就想试一试在一个100×100的围棋盘上任选两点A、BA点放上黑子B点放上白子代表两匹马。棋子可以按“日”字走也可以按“田”字走俩人一个走黑马一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时谁获胜。现在他请你帮忙给你A、B两点的坐标想知道两个位置到1,1点可能的最少步数。【输入】A、B两点的坐标。【输出】最少步数。【输入样例】12 16 18 10【输出样例】8 91. 题目背景在经典的搜索问题中我们经常遇到“马走日”的最短路问题。但如果有位小学生突发奇想规定棋子不仅能走“日”还能像象一样走“田”字这道题该怎么解呢题目大意地图的围棋盘。移动规则日中国象棋马的走法例如坐标偏移。田向四个斜角方向飞两格即坐标偏移。目标给定起点A和B分别求它们走到左上角(1,1)的最少步数。2. 算法分析广度优先搜索 (BFS)这是一个典型的无权图最短路径问题。在一个网格图中求从起点到终点的最少步数且每一步的代价都是1BFS广度优先搜索是最优解。核心难点方向数组的构建普通的马只有 8 个跳跃方向但这道题增加了“田”字走法。我们需要正确定义 12 个方向的偏移量。“日”字走法 (8种)(1, 2), (1, -2), (-1, 2), (-1, -2)(2, 1), (2, -1), (-2, 1), (-2, -1)“田”字走法 (4种)(2, 2), (2, -2), (-2, 2), (-2, -2)实现细节状态记录 (vis数组)vis[x][y]既用来标记是否访问过也用来记录步数。技巧为了区分“未访问0”和“起点的步数0”我们将起点的vis设为 1。最终输出结果时由vis[1][1]-1还原真实步数。局部变量优化将queue定义在bfs函数内部确保每次调用函数时队列都是空的避免多组数据互相污染。提前退出一旦从队列中取出的点坐标为(1,1)说明最短路已找到直接return减少不必要的计算。3. 完整代码#include iostream #include queue #include cstring using namespace std; int vis[110][110];//记录走到每个点需要的步数 //方向数组前8个是“日”后4个是“田” //日: (±1, ±2), (±2, ±1) //田: (±2, ±2) int dx[12]{2,-2,2,-2,1,-1,1,-1,2,2,-2,-2}; int dy[12]{1,1,-1,-1,2,2,-2,-2,2,-2,2,-2}; struct node{ int x,y; }; queuenode q; void bfs(int x,int y){//马现在的位置 queuenode q; node tmp; tmp.xx; tmp.yy; q.push(tmp);//队首入队 while(!q.empty()){ tmpq.front();//访问队首 q.pop();//队首出队 //如果已经从队列里取出了(1,1)说明最短路已经找到了 //注意这里是在取出时判断或者在入队时判断都可以 if(tmp.x1tmp.y1) return; for(int i0;i12;i){ int nxtmp.xdx[i]; int nytmp.ydy[i]; // 边界判断判断是否已经走过 if(nx1nx100ny1ny100vis[nx][ny]0){ vis[nx][ny]vis[tmp.x][tmp.y]1; q.push({nx,ny}); } } } } int main(){ int xa,ya,xb,yb; cinxayaxbyb; vis[xa][ya]1; bfs(xa,ya); coutvis[1][1]-1endl; memset(vis,0,sizeof(vis)); vis[xb][yb]1; bfs(xb,yb); coutvis[1][1]-1endl; }4. 总结多组数据重置本题虽然是一次运行求两个点但相当于两组数据。在计算完A点后必须使用memset(vis,0,sizeof(vis))清空状态数组否则计算B点时会受到A点遗留数据的干扰。队列作用域如果将queue定义为全局变量记得在每次bfs开始前清空它或者像我代码中一样定义为局部变量。方向数组写12个方向时容易手误写错正负号建议按规律分组写如代码中的注释所示并在草稿纸上简单验证。