POJ 1915 Knight Moves(BFS+STL)

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?
The Problem
Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
For people not familiar with chess, the possible knight moves are shown in Figure 1.

　　　　　　　　　　　　　　　　　　　　　　

Input

Output

Sample Input

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

Sample Output

5
28
0

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 350
using namespace std;

int n;
int x1,x2,y1,y2;


struct node{
    int x;
    int y;
    int sum;
    node(int a,int b,int c)
    {
        x=a;
        y=b;
        sum=c;
    }

};

int go[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}};
int vis[310][310];

int BFS()
{
    queue<node> que;
    memset(vis,0,sizeof vis);
    que.push(node(x1,y1,0));
    vis[x1][y1]=1;
    while(!que.empty())
    {
        node temp=que.front();
        for(int i=0;i<8;i++)
        {
            int x0=temp.x+go[i][0];
            int y0=temp.y+go[i][1];
            int sum0=temp.sum+1;
            if(x0>=0&&x0<n&&y0>=0&&y0<n)
            {
                if(x0==x2&&y0==y2) return sum0;
                else if(!vis[x0][y0])
                {
                    que.push(node(x0,y0,sum0));
                    vis[x0][y0]=1;
                }
            }
        }
        que.pop();
    }

    return 0;

}



int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d%d",&n,&x1,&y1,&x2,&y2);

        if(x1==x2&&y1==y2)
            printf("0\n");
        else
            printf("%d\n",BFS());
    }

    return 0;

}