Horse Pro（带负坐标的bfs搜索）

Horse Pro

bfs搜索，但图中存在负值坐标，两种方法解决。

• 用数组标记，将原点设为300，300
• 用map标记

http://oj.jxust.edu.cn/contest/Problem?id=1689&pid=5

#include <iostream>

#include <cstdio>

#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 100000 + 5;

int bx,by,e2,ey;

int vis[605][605];

int dir[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2};

struct Node

{

    int x;

    int y;

    int len;

};

int bfs()

{

    Node next;

    next.x=bx;next.y=by;next.len=0;

    queue<Node> q;

    q.push(next);

    while(!q.empty())

    {

        Node front;

        front =q.front();

        if(front.len>100) return -1;

        q.pop();

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

        {

            next.x=front.x+dir[i][0],next.y=front.y+dir[i][1],next.len=front.len+1;

            if(vis[next.x][next.y]) continue;

            if(next.x==e2&&next.y==ey) return next.len;

            q.push(next);

            vis[next.x][next.y]=1;

        }

    }

    return -1;

}

int main() {

    scanf("%d%d%d%d",&bx,&by,&e2,&ey);

    e2=e2-bx+300;ey=ey-by+300;

    bx=300;by=300;

    int res=bfs();

    printf("%d\n",res);

    return 0;

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <map>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

const int maxn = 100100;

const int inf = 0x3f3f3f3f;

const int M = 1e9+7;

int to[8][2] = {2,1,2,-1,-2,1,-2,-1,1,2,-1,2,1,-2,-1,-2};

int a,b,c,d;

struct node

{

    int x,y,z;

};

map<pair<int,int>, int> m;

int bfs()

{

    node now,nex;

    now.x = a,now.y= b,now.z = 0;

    std::queue<node> q;

    q.push(now);

    while(!q.empty())

    {

        now = q.front();

        q.pop();

        if(now.x == c && now.y==d) return now.z;

        if(now.z > 100) break;

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

        {

            nex.x = now.x+to[i][0];

            nex.y = now.y+to[i][1];

            if(m[make_pair(nex.x,nex.y)]) continue;

            m[make_pair(nex.x,nex.y)]=1;

            nex.z = now.z+1;

            q.push(nex);

        }

    }

    return -1;

}

int main()

{

    scanf("%d%d%d%d", &a,&b,&c,&d);

    c=c-a;d=d-b;

    a=0,b=0;

    printf("%d\n", bfs());

    return 0;

}