POJ 1915 經典馬步 雙向bfs

#include <iostream>   
#include <algorithm>   
#include <cmath>   
#include <cstdio>   
#include <cstdlib>   
#include <cstring>   
#include <string>   
#include <vector>   
#include <set>   
#include <queue>   
#include <stack>   
#include <climits>//形如INT_MAX一類的   
#define MAX 333   
#define INF 0x7FFFFFFF   
# define eps 1e-5   
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛   
using namespace std;  
  
int num1[MAX][MAX],num2[MAX][MAX];  
int map[MAX][MAX];  
int dirx[8] = {2, 2, -2, -2, 1, 1, -1, -1};  
int diry[8] = {-1, 1, -1, 1, -2, 2, -2, 2};  
  
struct node  
{  
    int x,y;  
}start,end;  
int n;  
void init()  
{  
    memset(map,0,sizeof(map));  
    memset(num1,-1,sizeof(num1));  
    memset(num2,-1,sizeof(num2));  
}  
  
bool inside(int x,int y)  
{  
    if(x<0 || x>=n || y<0 || y>=n)  
        return false;  
    return true;  
}  
void dbfs()  
{  
    queue<node>p,q;  
    p.push(start);  
    num1[start.x][start.y] = 0;  
    q.push(end);  
    num2[end.x][end.y] = 0;  
    while(!p.empty() && !q.empty())  
    {  
        node t,tt;  
        int size = p.size();  
        while(size--)  
        {  
            t = p.front();  
            p.pop();  
            if(inside(t.x,t.y) && num2[t.x][t.y] != -1)  
            {  
                printf("%d\n",num1[t.x][t.y] + num2[t.x][t.y]);  
                return ;  
            }  
            for(int i=0; i<8; i++)  
            {  
                tt.x = t.x + dirx[i];  
                tt.y = t.y + diry[i];  
                if(inside(tt.x,tt.y) && num2[tt.x][tt.y] != -1)  
                {  
                    printf("%d\n",num1[t.x][t.y] + 1 + num2[tt.x][tt.y]);  
                    return ;  
                }  
                if(inside(tt.x,tt.y) && num1[tt.x][tt.y] == -1)  
                {  
                    num1[tt.x][tt.y] = num1[t.x][t.y] + 1;  
                    p.push(tt);  
                }  
            }  
        }  
        size = q.size();  
        while(size --)  
        {  
            t = q.front();  
            q.pop();  
            if(inside(t.x,t.y) && num1[t.x][t.y] != -1)  
            {  
                printf("%d\n",num2[t.x][t.y] + num1[t.x][t.y] );  
                return ;  
            }  
            for(int i=0; i<8; i++)  
            {  
                tt.x = t.x + dirx[i];  
                tt.y = t.y + diry[i];  
                if(inside(tt.x,tt.y) && num1[tt.x][tt.y] != -1)  
                {  
                    printf("%d\n",num2[t.x][t.y] + 1 + num1[tt.x][tt.y]);  
                    return ;  
                }  
                if(inside(tt.x,tt.y) && num2[tt.x][tt.y] == -1)  
                {  
                    num2[tt.x][tt.y] = num2[t.x][t.y] + 1;  
                    q.push(tt);  
                }  
            }  
        }  
    }  
}  
int main()  
{  
    int t;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d",&n);  
        init();  
        scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);  
        dbfs();  
    }  
    return 0;  
}  

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一類的
#define MAX 333
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛
using namespace std;

int num1[MAX][MAX],num2[MAX][MAX];
int map[MAX][MAX];
int dirx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int diry[8] = {-1, 1, -1, 1, -2, 2, -2, 2};

struct node
{
    int x,y;
}start,end;
int n;
void init()
{
    memset(map,0,sizeof(map));
    memset(num1,-1,sizeof(num1));
    memset(num2,-1,sizeof(num2));
}

bool inside(int x,int y)
{
    if(x<0 || x>=n || y<0 || y>=n)
        return false;
    return true;
}
void dbfs()
{
    queue<node>p,q;
    p.push(start);
    num1[start.x][start.y] = 0;
    q.push(end);
    num2[end.x][end.y] = 0;
    while(!p.empty() && !q.empty())
    {
        node t,tt;
        int size = p.size();
        while(size--)
        {
            t = p.front();
            p.pop();
            if(inside(t.x,t.y) && num2[t.x][t.y] != -1)
            {
                printf("%d\n",num1[t.x][t.y] + num2[t.x][t.y]);
                return ;
            }
            for(int i=0; i<8; i++)
            {
                tt.x = t.x + dirx[i];
                tt.y = t.y + diry[i];
                if(inside(tt.x,tt.y) && num2[tt.x][tt.y] != -1)
                {
                    printf("%d\n",num1[t.x][t.y] + 1 + num2[tt.x][tt.y]);
                    return ;
                }
                if(inside(tt.x,tt.y) && num1[tt.x][tt.y] == -1)
                {
                    num1[tt.x][tt.y] = num1[t.x][t.y] + 1;
                    p.push(tt);
                }
            }
        }
        size = q.size();
        while(size --)
        {
            t = q.front();
            q.pop();
            if(inside(t.x,t.y) && num1[t.x][t.y] != -1)
            {
                printf("%d\n",num2[t.x][t.y] + num1[t.x][t.y] );
                return ;
            }
            for(int i=0; i<8; i++)
            {
                tt.x = t.x + dirx[i];
                tt.y = t.y + diry[i];
                if(inside(tt.x,tt.y) && num1[tt.x][tt.y] != -1)
                {
                    printf("%d\n",num2[t.x][t.y] + 1 + num1[tt.x][tt.y]);
                    return ;
                }
                if(inside(tt.x,tt.y) && num2[tt.x][tt.y] == -1)
                {
                    num2[tt.x][tt.y] = num2[t.x][t.y] + 1;
                    q.push(tt);
                }
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init();
        scanf("%d%d%d%d",&start.x,&start.y,&end.x,&end.y);
        dbfs();
    }
    return 0;
}