#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;
}
সোমবার, ৬ জানুয়ারী, ২০১৪
Solution code of uva-10067
Labels:
uva solution
এতে সদস্যতা:
মন্তব্যগুলি পোস্ট করুন (Atom)
0 comments:
একটি মন্তব্য পোস্ট করুন