F: Horse Pro 马走棋盘 BFS

F: Horse Pro

豆豆也已经开始学着玩象棋了，现在豆豆已经搞清楚马的走法了，但是豆豆不能确定能否在 100

步以内从一个点到达另一个点（假设棋盘无限大）。

Input

第一行输入两个整数 x1,y1

表示当前马所在的位置。

第二行输入两个整数 x2,y2

表示豆豆想把马走在的位置。

−10000≤x1,x2,y1,y2≤10000

 

Output

如果能够在100步以内（包括100步）从(x1,y1)

到达 (x2,y2) 则输出到达所需要的最小步数，否则输出 −1

 

Sample Input

1 1

2 3

Sample Output

1

#include<iostream>

#include<algorithm>

#include<vector>

#include<math.h>

#include<stdio.h>

#include<string.h>

#include<map>

#include<queue>

#include<utility>

#define ll long long

using namespace std;

int dir[][] = {, , , , , -, , -, -, , -, , -, -, -, -};

int sx,sy,ex,ey;

struct node

{

    int x;

    int y;

    int dep;

};

map<pair<int,int>,int>m;//标记点是否走过,因为坐标有负数，不能用数组

/*

一开始是想用结构体的，map<node,int>m会编译报错，因为map是内部有序的

如果使用结构体的话，应该先重在小于号 > 使结构体保持有序

*/

int bfs()

{

    queue<node>p;

    node temp;

    temp.x=sx;

    temp.y=sy;

    temp.dep=;

    p.push(temp);

    while(!p.empty())

    {

        node now=p.front();

        p.pop();

        if(now.dep>)

            return -;

        if(now.x==ex&&now.y==ey)

            return now.dep;

        for(int i=;i<;i++)

        {

            node tmp=now;

            tmp.x=tmp.x+dir[i][];

            tmp.y=tmp.y+dir[i][];

            pair<int,int>d=make_pair(tmp.x,tmp.y);

            if(m[d])//标记点

                continue;

            m[d]=;

            tmp.dep++;

            p.push(tmp);

        }

    }

}

int main()

{

    cin>>sx>>sy>>ex>>ey;

    int ans=bfs();

    cout<<ans<<endl;

    return ;

}

F: Horse Pro 马走棋盘 BFS的相关教程结束。