#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
#define inf 1000000

int hash[7000000];
int hash2[7000000];

int ten[]={0,100000,10000,1000,100,10,1};

int code,final;

int stackStep,stackStep2;


int state[7000000];
int state2[7000000];


int BfsDual(int code, int final, int step) {
    int tpCode;
    char tChar[8],t;
    int tpPos,hashnum;
    
    int iter=-1,top=-1;
    int iter2=-1,top2=-1;
    int i,j;
    
    top++;
    state[top]=code;
    hash[code]=true;
    
    for(i=0; i<=5; i++){
        top2++;
        state2[top2]=final;
        hash2[final]=true;
        final+=inf;
    } 
    
    
    stackStep=0; 
    stackStep2=5;
     
    
while(1){
        
    step++;
    while(iter!=stackStep){           
        iter++; 
        tpPos=state[iter]/inf; 
        tpCode=state[iter]; 
        if(tpPos!=1){
            itoa(tpCode,tChar,10);
            t=tChar[1]; tChar[1]=tChar[tpPos]; tChar[tpPos]=t;
            hashnum=atoi(tChar);     
            if(!hash[hashnum]){
                if(hash2[hashnum]) { return step; }    
                hash[hashnum]=true;
                top++;
                state[top]=hashnum;
            }
        }
        if(tpPos!=6){ 
            itoa(tpCode,tChar,10);
            t=tChar[6]; tChar[6]=tChar[tpPos]; tChar[tpPos]=t;
            hashnum=atoi(tChar);          
            if(!hash[hashnum]){
                if(hash2[hashnum]) { return step; }
                hash[hashnum]=true;
                top++;
                state[top]=hashnum;
            }      
        }       
        if(tpPos!=6){
            hashnum=tpCode+inf;
            if(!hash[hashnum]) {
                if(hash2[hashnum]) { return step; }
                hash[hashnum]=true;
                top++;
                state[top]=hashnum;
            }
        }
         i=(tpCode/ten[tpPos])%10;
        if(i!=9){ 
            hashnum=tpCode+ten[tpPos];
            if(!hash[hashnum]) {
                if(hash2[hashnum]) {return step;}
                hash[hashnum]=true;
                top++;
                state[top]=hashnum;
            }
        }
        if(i!=0){                                
            hashnum=tpCode-ten[tpPos];
            
            if(!hash[hashnum]) {
                if(hash2[hashnum]) { return step;}
                hash[hashnum]=true;
                top++;
                state[top]=hashnum; 
            } 
        }
    }
    stackStep=top;    
        
        
    step++;
    while(iter2!=stackStep2){     
         
        iter2++; 
        tpPos=state2[iter2]/inf; 
        tpCode=state2[iter2];       
        if(tpPos!=1){
            itoa(tpCode,tChar,10);
            t=tChar[1]; tChar[1]=tChar[tpPos]; tChar[tpPos]=t;
            hashnum=atoi(tChar);
            if(!hash2[hashnum]){
                if(hash[hashnum]) {return step;}    
                hash2[hashnum]=true;
                top2++;
                state2[top2]=hashnum; 
            }    
        }
        if(tpPos!=6){    
            itoa(tpCode,tChar,10);
            t=tChar[6]; tChar[6]=tChar[tpPos]; tChar[tpPos]=t;
            hashnum=atoi(tChar);
            if(!hash2[hashnum]){
                if(hash[hashnum]) {return step;}    
                hash2[hashnum]=true;
                top2++;
                state2[top2]=hashnum;
            }     
        }        
        if(tpPos!=1){     
            hashnum=tpCode-inf;
            if(!hash2[hashnum]) {
               if(hash[hashnum]) {return step;}
                hash2[hashnum]=true;
                top2++;
                state2[top2]=hashnum;
            }
        }
        i=(tpCode/ten[tpPos])%10;           
        if(i!=9){ 
            hashnum=tpCode+ten[tpPos];
            if(!hash2[hashnum]) {
                if(hash[hashnum]) {return step;}
                hash2[hashnum]=true;
                top2++;
                state2[top2]=hashnum;
            }
        }
        if(i!=0){           
            hashnum=tpCode-ten[tpPos];
            if(!hash2[hashnum]) {
                if(hash[hashnum]) {return step;}
                hash2[hashnum]=true;
                top2++;
                state2[top2]=hashnum;
            }  
        }
    }
    stackStep2=top2;
        
} 
   
}    


int main() {
    scanf("%d %d",&code,&final);
    code+=inf;
    final+=inf;
    
    if(code==final) printf("0");
    else printf("%d",BfsDual(code,final,0));
    system("pause");
  return 0;
}

改进后的 还是不行

• 终于ac (9) ych_tiger 2007-05-16 20:23:10