Pages

সোমবার, ৬ জানুয়ারী, ২০১৪

Solution code of uva-10067


#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
struct node
{
    int a,b,c,d;
}data,des;
int main()
{
   //freopen("c:\\temp\\in.txt","r",stdin);
  int test_case;
  scanf("%d",&test_case);
     int a_x[]={-1,1,0,0,0,0,0,0};
     int a_y[]={0,0,0,0,0,0,1,-1};
     int a_z[]={0,0,1,-1,0,0,0,0};
     int a_l[]={0,0,0,0,1,-1,0,0};
  while(test_case--)
  {
     cin>>data.a>>data.b>>data.c>>data.d;
     queue<node>q;
     q.push(data);
     int coun[10][10][10][10];
     int  cons[10][10][10][10];
     for(int i=0;i<=9;i++)
        for(int j=0;j<=9;j++)
          for(int k=0;k<=9;k++)
           for(int l=0;l<=9;l++)
     {
         coun[i][j][k][l]=0;
        cons[i][j][k][l]=0;
     }
     coun[data.a][data.b][data.c][data.d]=1;
     cin>>des.a>>des.b>>des.c>>des.d;
     int n;
     scanf("%d",&n);
     while(n--)
     {
        cin>>data.a>>data.b>>data.c>>data.d;
        cons[data.a][data.b][data.c][data.d]=1;
     }
     int found=0;
      node pop=q.front();
        if(des.a==pop.a && des.b==pop.b && des.c==pop.c && des.d==pop.d)
            found=1;
     while(!q.empty() && !found)
     {
//         cout<<"p"<<endl;
         node pop=q.front();q.pop();
         for(int i=0;i<8;i++)
         {
             data.a=(pop.a+a_x[i])%10;
             if(data.a==-1)data.a=9;
             data.b=(pop.b+a_y[i])%10;
               if(data.b==-1)data.b=9;
             data.c=(pop.c+a_z[i])%10;
               if(data.c==-1)data.c=9;
             data.d=(pop.d+a_l[i])%10;
               if(data.d==-1)data.d=9;
             //cout<< data.a<<" "<<data.b<<" "<<data.c<<" "<<data.d<<endl;
             if(coun[data.a][data.b][data.c][data.d]==0 && cons[data.a][data.b][data.c][data.d]==0)
             {
                 coun[data.a][data.b][data.c][data.d]=coun[pop.a][pop.b][pop.c][pop.d]+1;
                         if(data.a==des.a && data.b==des.b && data.c==des.c && data.d==des.d)
                {
              found=1;break;
                     }
                 q.push(data);
             }
         }
     }
     if(found)
        cout<<coun[des.a][des.b][des.c][des.d]-1;
     else cout<<-1;
     cout<<endl;
  }
  return 0;
}

0 comments:

একটি মন্তব্য পোস্ট করুন