HDU1195 Open the Lock单向广搜-白红宇

HDU1195 Open the Lock单向广搜

阅读量：6025 次

发布时间：2019-06-20

本文共 1444 字，大约阅读时间需要 4 分钟。

/*RESCUE*/#include 
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define maxn 220char start[6],end[6];bool vis[10005];struct re{ int str[4]; int num; re(const char *a) { num=0; for(int i=0; i<4; ++i) str[i]=a[i]-'0'; } int cal() { return str[0]*1000+str[1]*100+str[2]*10+str[3]; } bool operator ==(const re &tt) const { for(int i=0; i<4; ++i) if(str[i]!=tt.str[i]) return false; return true; }};int main(){ int t; scanf("%d",&t); while(t--) { scanf("%s%s",start,end); re End(end); queue
            
              Q; Q.push(start); memset(vis,false,sizeof(vis)); while(!Q.empty()) { re Beg=Q.front(); Q.pop(); if(Beg==End) { printf("%d\n",Beg.num); break; } Beg.num++; int pp; for(int pos=0; pos<4; pos++) { Beg.str[pos]++; if(Beg.str[pos]==10) Beg.str[pos]=1; if(!vis[pp=Beg.cal()]) { vis[pp]=true; Q.push(Beg); } Beg.str[pos]--; if(Beg.str[pos]==0) Beg.str[pos]=9; Beg.str[pos]--; if(Beg.str[pos]==0) Beg.str[pos]=9; if(!vis[pp=Beg.cal()]) { vis[pp]=true; Q.push(Beg); } Beg.str[pos]++; if(Beg.str[pos]==10) Beg.str[pos]=1; } for(int pos=0; pos<3; pos++) { int tmp=Beg.str[pos]; Beg.str[pos]=Beg.str[pos+1]; Beg.str[pos+1]=tmp; if(!vis[pp=Beg.cal()]) { vis[pp]=true; Q.push(Beg); } tmp=Beg.str[pos]; Beg.str[pos]=Beg.str[pos+1]; Beg.str[pos+1]=tmp; } } }}