10067 - Playing with Wheels

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define M 10000
using namespace std;

int BFS(int,int,int,int,int);
int Forbid[M];
int next[8][4]={{1,0,0,0},{-1,0,0,0},{0,1,0,0},{0,-1,0,0},{0,0,1,0},{0,0,-1,0},{0,0,0,1},{0,0,0,-1}};

int main()
{
    int t,a,b,c,d,sa,sb,sc,sd,i,n,N,T;
    //freopen("in.txt","r",stdin);
    scanf("%d",&t);

    while(t--)
    {
        scanf("%d%d%d%d",&sa,&sb,&sc,&sd);
        scanf("%d%d%d%d",&a,&b,&c,&d);
        T = 1000*a + 100*b + 10*c + d;

        memset(Forbid,0,sizeof(Forbid));

        scanf("%d",&n);
        for(i = 0;i<n;i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            d = 1000*a + 100*b + 10*c + d;
            Forbid[d] = 1;
        }

        N = BFS(sa,sb,sc,sd,T);
        printf("%d\n",N);
    }
    return 0;
}

int BFS(int sa,int sb,int sc,int sd,int T)
{
    int a,b,c,d,ta,tb,tc,td,tmp,t,ok=1,i;
    int D[M];
    queue<int>Q;

    tmp = 1000*sa + 100*sb + 10*sc + sd;
    if(Forbid[tmp])return -1;
    if(tmp == T)return 0;
    D[tmp]=0;

    Q.push(sa);Q.push(sb);
    Q.push(sc);Q.push(sd);

    while(!Q.empty())
    {
        a = Q.front();Q.pop();
        b = Q.front();Q.pop();
        c = Q.front();Q.pop();
        d = Q.front();Q.pop();
        t = 1000*a + 100*b + 10*c + d;

        for(i=0;i<8;i++)
        {
            ta = a + next[i][0];
            tb = b + next[i][1];
            tc = c + next[i][2];
            td = d + next[i][3];

            if(ta>9)ta=0;
            if(ta<0)ta=9;
           
            if(tb>9)tb=0;
            if(tb<0)tb=9;
           
            if(tc>9)tc=0;
            if(tc<0)tc=9;
           
            if(td>9)td=0;
            if(td<0)td=9;

            tmp = 1000*ta + 100*tb + 10*tc + td;
            if(Forbid[tmp]==0)
            {
                D[tmp] = D[t] + 1;
                if(tmp == T)return D[tmp];

                Forbid[tmp] = 1;
                Q.push(ta);Q.push(tb);
                Q.push(tc);Q.push(td);
            }
        }
    }
    return -1;
}