2021 icpc 沈阳站 J

 数字锁问题

运用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;
}

最后

以上就是老实板栗为你收集整理的2021 icpc 沈阳站 J的全部内容，希望文章能够帮你解决2021 icpc 沈阳站 J所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。