|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <queue> using namespace std; bool visit[10][10][10][10]; int arr[3]={0,1,-1}; struct states{ int a,b,c,d; int step; }; int main() { int t,n,stp; states tmp; int tw,tx,ty,tz; int a,b,c,d,x,y,w,z; cin>>t; while(t--) { states src,trgt,tmp; for(int i=0;i<10;i++) for(int j=0;j<10;j++) for(int k=0;k<10;k++) for(int l=0;l<10;l++) visit[i][j][k][l]=0; cin>>a>>b>>c>>d; src.a=a; src.b=b; src.c=c; src.d=d; src.step=0; cin>>a>>b>>c>>d; trgt.a=a; trgt.b=b; trgt.c=c; trgt.d=d; trgt.step=-1; cin>>n; for(int i=0;i<n;i++) { cin>>a>>b>>c>>d; visit[a][b][c][d]=1; } queue<states> q; q.push(src); while(!q.empty()) { tmp = q.front();q.pop(); w=tmp.a; x=tmp.b; y=tmp.c; z=tmp.d; stp=tmp.step; visit[w][x][y][z]=1; if(w==trgt.a && x==trgt.b && y==trgt.c && z==trgt.d) { trgt.step=stp; break; } int tarr[4]={w,x,y,z}; for(int i=0;i<4;i++) { int xx=tarr[i]; tarr[i]=(tarr[i]+1)%10; if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0) { tmp.a=tarr[0]; tmp.b=tarr[1]; tmp.c=tarr[2]; tmp.d=tarr[3]; tmp.step=stp+1; visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1; q.push(tmp); } tarr[i]=xx; tarr[i]=((xx-1)<0?9:(xx-1)%10); if(visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]==0) { tmp.a=tarr[0]; tmp.b=tarr[1]; tmp.c=tarr[2]; tmp.d=tarr[3]; tmp.step=stp+1; visit[tarr[0]][tarr[1]][tarr[2]][tarr[3]]=1; q.push(tmp); } tarr[i]=xx; } //cout<<"sdjj\n"; } if(trgt.step!=-1) cout<<trgt.step<<"\n"; else cout<<-1<<"\n"; } return 0; } |