曼哈顿距离:经常可以用来替代广搜,但是前提是只能上下左右四个方向移动,并且只研究最短路程的结果不研究行走的过程
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int w,m,n;
cin>>w>>m>>n;
m--;n--;//让数组下标从0开始
int x1,x2,y1,y2;//x1,y1表示m的位置,x2,y2表示n的位置
x1=m/w,x2=n/w;
y1=m%w,y2=n%w;
if(x1%2==0)//因为是蛇形矩阵偶数行则颠倒一下位置
y1=w-1-y1;//因为下标从0开始,所以最后一个的坐标一定是n-1
if(x2%2==0)
y2=w-1-y2;
cout<<abs(x1-x2)+abs(y1-y2);
return 0;
}