【题目描述】
在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（100×100）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点可能的最少步数。
【输入】
A、B两点的坐标。
【输出】
最少步数。
【输入样例】
12 16 18 10【输出样例】
8 91. 题目背景
在经典的搜索问题中，我们经常遇到“马走日”的最短路问题。但如果有位小学生突发奇想，规定棋子不仅能走“日”，还能像象一样走“田”字，这道题该怎么解呢？
题目大意：
地图：
的围棋盘。
移动规则：
日：中国象棋马的走法（例如坐标偏移
）。
田：向四个斜角方向飞两格（即坐标偏移
）。
目标：给定起点A和B，分别求它们走到左上角(1,1)的最少步数。
2. 算法分析：广度优先搜索 (BFS)
这是一个典型的无权图最短路径问题。
在一个网格图中，求从起点到终点的最少步数，且每一步的代价都是1，BFS（广度优先搜索）是最优解。
核心难点：方向数组的构建
普通的马只有 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; }; queue<node> q; void bfs(int x,int y){//马现在的位置 queue<node> q; node tmp; tmp.x=x; tmp.y=y; q.push(tmp);//队首入队 while(!q.empty()){ tmp=q.front();//访问队首 q.pop();//队首出队 //如果已经从队列里取出了(1,1)，说明最短路已经找到了 //注意：这里是在取出时判断，或者在入队时判断都可以 if(tmp.x==1&&tmp.y==1) return; for(int i=0;i<12;i++){ int nx=tmp.x+dx[i]; int ny=tmp.y+dy[i]; // 边界判断+判断是否已经走过 if(nx>=1&&nx<=100&&ny>=1&&ny<=100&&vis[nx][ny]==0){ vis[nx][ny]=vis[tmp.x][tmp.y]+1; q.push({nx,ny}); } } } } int main(){ int xa,ya,xb,yb; cin>>xa>>ya>>xb>>yb; vis[xa][ya]=1; bfs(xa,ya); cout<<vis[1][1]-1<<endl; memset(vis,0,sizeof(vis)); vis[xb][yb]=1; bfs(xb,yb); cout<<vis[1][1]-1<<endl; }4. 总结
多组数据重置：
本题虽然是一次运行求两个点，但相当于两组数据。在计算完A点后，必须使用
memset(vis,0,sizeof(vis))清空状态数组，否则计算B点时会受到A点遗留数据的干扰。队列作用域：
如果将
queue定义为全局变量，记得在每次bfs开始前清空它（或者像我代码中一样定义为局部变量）。方向数组：
写12个方向时容易手误写错正负号，建议按规律分组写（如代码中的注释所示），并在草稿纸上简单验证。
