数字锁问题

运用bfs 打表。

把所有情况看为从0000开始变换。例如1234-2345，就是0000-1111。总共有10^4 种情况，打表。

J： Luggage Lock

#include<bits/stdc++.h>
using namespace std;
int v[10000]={0};
int m[10000]={0};
int change(int k[4]){return 1000*k[0]+100*k[1]+10*k[2]+k[3];
}
int w[20][4]={0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,0,9,0,0,9,0,0,9,0,0,9,0,0,0,0,0,1,1,0,1,1,0,1,1,0,0,0,0,9,9,0,9,9,0,9,9,0,0,0,1,1,1,1,1,1,0,0,9,9,9,9,9,9,0,1,1,1,1,9,9,9,9};
void bfs(){queue <int> q;int v0=0;int t,n[4],t1,t0;q.push(v0);v[v0]=1;while(!q.empty()){t=q.front();t0=t;q.pop();for(int i=0;i<4;i++){n[3-i]=t%10;t/=10;}        for(int i=0;i<20;i++){t1=((n[0]+w[i][0]+10)%10)*1000+((n[1]+w[i][1]+10)%10)*100+((n[2]+w[i][2]+10)%10)*10+((n[3]+w[i][3]+10)%10);if(!v[t1]){v[t1]=1;q.push(t1);m[t1]=m[t0]+1;}}}
}
int main(){int i,j,t,T,a0,b0,a[4],b[4];int k[4];bfs();cin>>T;while(T--){cin>>a0>>b0;for(i=0;i<4;i++){a[3-i]=a0%10;a0/=10;b[3-i]=b0%10;b0/=10;k[3-i]=(b[3-i]-a[3-i]+10)%10;}t=change(k);cout<<m[t]<<endl;}return 0;
}