Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

TL 哪位有时间帮我看看啊谢谢

Posted by ych_tiger at 2007-05-15 20:41:44 on Problem 1184

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

bool hash[7000000];
bool hash2[7000000];

char code[8],final[8];

int stackStep,stackStep2;

char state[7000000][8];
char state2[7000000][8];


int BfsDual(char *code, char *final, int step) {
    char tpCode[8],t;
    int tpPos,hashnum;
    
    int iter=-1,top=-1;
    int iter2=-1,top2=-1;
    int flag=0; flag=1;

    int i;
    
    top++;
    strcpy(state[top],code);
    hash[atoi(code)]=true;
    
    for(i=0; i<=5; i++){
        top2++;
        strcpy(state2[top2],final);
        hash2[atoi(final)]=true;
        final[0]++;
    } 
    
    hash[atoi(final)]=true;
    stackStep=0; 
    stackStep2=5;
     
    
while(1){
        
    step++;
    while(iter!=stackStep){
            
        iter++; 
        tpPos=state[iter][0]-'0'; 
        strcpy(tpCode,state[iter]);
        
        if(tpPos!=1){
            t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
            hashnum=atoi(tpCode);
            if(!hash[hashnum]){
                if(hash2[hashnum]) {
               return step;
                }    
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode);
            }
            t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
        }
        if(tpPos!=6){    
            t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;
            hashnum=atoi(tpCode);
            if(!hash[hashnum]){
                if(hash2[hashnum]) {
                     return step;
                }
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode);
            }
            t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;       
        }        
        if(tpPos!=1){
            tpCode[0]--;       
            hashnum=atoi(tpCode);
            if(!hash[hashnum]) {
                if(hash2[hashnum]) {
                     return step;
                }
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode);
            }
            tpCode[0]++;
        }       
        if(tpPos!=6){
            tpCode[0]++;
            hashnum=atoi(tpCode);
            if(!hash[hashnum]) {
                if(hash2[hashnum]) {
                     return step;
                }
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode);
            }
            tpCode[0]--;
        }       
        if(tpCode[tpPos]!='9'){  
            tpCode[tpPos]++;
            hashnum=atoi(tpCode);
            if(!hash[hashnum]) {
                if(hash2[hashnum]) {
                     return step;
                }
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode);
            }
            tpCode[tpPos]--;
        }
        if(tpCode[tpPos]!='0'){           
            tpCode[tpPos]--;
            hashnum=atoi(tpCode);
            if(!hash[hashnum]) {
                if(hash2[hashnum]) {
                     return step;
                }
                hash[hashnum]=true;
                top++;
                strcpy(state[top],tpCode); 
            }
            tpCode[tpPos]++;   
        }
    }
    stackStep=top;    
        
        
    step++;
    while(iter2!=stackStep2){     
                    
        iter2++; 
        tpPos=state2[iter2][0]-'0'; 
        strcpy(tpCode,state2[iter2]);
        
        if(iter2==stackStep2){
            step++;
            stackStep2=top2+1;
        }    
        
        if(tpPos!=1){
            t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]){
                if(hash[hashnum]) {
                     return step;
                }    
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode);
            }
            t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
        }
        if(tpPos!=6){    
            t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]){
                if(hash[hashnum]) {
                     return step;
                }    
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode);
            }
            t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;       
        }        
        if(tpPos!=1){
            tpCode[0]--;       
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]) {
               if(hash[hashnum]) {
                    return step;
                }
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode);
            }
            tpCode[0]++;
        }       
        if(tpPos!=6){
            tpCode[0]++;
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]) {
                if(hash[hashnum]) {
                     return step;
                }
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode);
            }
            tpCode[0]--;
        }       
        if(tpCode[tpPos]!='9'){  
            tpCode[tpPos]++;
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]) {
                if(hash[hashnum]) {
                     return step;
                }
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode);
            }
            tpCode[tpPos]--;
        }
        if(tpCode[tpPos]!='0'){           
            tpCode[tpPos]--;
            hashnum=atoi(tpCode);
            if(!hash2[hashnum]) {
                if(hash[hashnum]) {
                     return step;
                }
                hash2[hashnum]=true;
                top2++;
                strcpy(state2[top2],tpCode); 
            }
            tpCode[tpPos]++;   
        }
    }
    stackStep2=top2;
        
    }    
}    


int main() {
    code[0]='1';
    final[0]='1';
    scanf("%s %s",&code[1],&final[1]);
    if(!strcmp(code,final)) printf("0");
    else printf("%d",BfsDual(code,final,0));
    system("pause");
  return 0;
}

Followed by:

改进后的还是不行 (4678) ych_tiger 2007-05-16 19:10:54
- 终于ac (9) ych_tiger 2007-05-16 20:23:10
写得太长了，我自己的都不想看第二眼，现在超时，超得跟鬼一样，受不了了 (0) zhou123 2009-08-05 16:11:47

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #define true 1
> #define false 0
> #define inf 1000000
> 
> bool hash[7000000];
> bool hash2[7000000];
> 
> char code[8],final[8];
> 
> int stackStep,stackStep2;
> 
> char state[7000000][8];
> char state2[7000000][8];
> 
> 
> int BfsDual(char *code, char *final, int step) {
>     char tpCode[8],t;
>     int tpPos,hashnum;
>     
>     int iter=-1,top=-1;
>     int iter2=-1,top2=-1;
>     int flag=0; flag=1;
> 
>     int i;
>     
>     top++;
>     strcpy(state[top],code);
>     hash[atoi(code)]=true;
>     
>     for(i=0; i<=5; i++){
>         top2++;
>         strcpy(state2[top2],final);
>         hash2[atoi(final)]=true;
>         final[0]++;
>     } 
>     
>     hash[atoi(final)]=true;
>     stackStep=0; 
>     stackStep2=5;
>      
>     
> while(1){
>         
>     step++;
>     while(iter!=stackStep){
>             
>         iter++; 
>         tpPos=state[iter][0]-'0'; 
>         strcpy(tpCode,state[iter]);
>         
>         if(tpPos!=1){
>             t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]){
>                 if(hash2[hashnum]) {
>                return step;
>                 }    
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode);
>             }
>             t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
>         }
>         if(tpPos!=6){    
>             t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]){
>                 if(hash2[hashnum]) {
>                      return step;
>                 }
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode);
>             }
>             t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;       
>         }        
>         if(tpPos!=1){
>             tpCode[0]--;       
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]) {
>                 if(hash2[hashnum]) {
>                      return step;
>                 }
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode);
>             }
>             tpCode[0]++;
>         }       
>         if(tpPos!=6){
>             tpCode[0]++;
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]) {
>                 if(hash2[hashnum]) {
>                      return step;
>                 }
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode);
>             }
>             tpCode[0]--;
>         }       
>         if(tpCode[tpPos]!='9'){  
>             tpCode[tpPos]++;
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]) {
>                 if(hash2[hashnum]) {
>                      return step;
>                 }
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode);
>             }
>             tpCode[tpPos]--;
>         }
>         if(tpCode[tpPos]!='0'){           
>             tpCode[tpPos]--;
>             hashnum=atoi(tpCode);
>             if(!hash[hashnum]) {
>                 if(hash2[hashnum]) {
>                      return step;
>                 }
>                 hash[hashnum]=true;
>                 top++;
>                 strcpy(state[top],tpCode); 
>             }
>             tpCode[tpPos]++;   
>         }
>     }
>     stackStep=top;    
>         
>         
>     step++;
>     while(iter2!=stackStep2){     
>                     
>         iter2++; 
>         tpPos=state2[iter2][0]-'0'; 
>         strcpy(tpCode,state2[iter2]);
>         
>         if(iter2==stackStep2){
>             step++;
>             stackStep2=top2+1;
>         }    
>         
>         if(tpPos!=1){
>             t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]){
>                 if(hash[hashnum]) {
>                      return step;
>                 }    
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode);
>             }
>             t=tpCode[1]; tpCode[1]=tpCode[tpPos]; tpCode[tpPos]=t;
>         }
>         if(tpPos!=6){    
>             t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]){
>                 if(hash[hashnum]) {
>                      return step;
>                 }    
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode);
>             }
>             t=tpCode[6]; tpCode[6]=tpCode[tpPos]; tpCode[tpPos]=t;       
>         }        
>         if(tpPos!=1){
>             tpCode[0]--;       
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]) {
>                if(hash[hashnum]) {
>                     return step;
>                 }
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode);
>             }
>             tpCode[0]++;
>         }       
>         if(tpPos!=6){
>             tpCode[0]++;
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]) {
>                 if(hash[hashnum]) {
>                      return step;
>                 }
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode);
>             }
>             tpCode[0]--;
>         }       
>         if(tpCode[tpPos]!='9'){  
>             tpCode[tpPos]++;
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]) {
>                 if(hash[hashnum]) {
>                      return step;
>                 }
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode);
>             }
>             tpCode[tpPos]--;
>         }
>         if(tpCode[tpPos]!='0'){           
>             tpCode[tpPos]--;
>             hashnum=atoi(tpCode);
>             if(!hash2[hashnum]) {
>                 if(hash[hashnum]) {
>                      return step;
>                 }
>                 hash2[hashnum]=true;
>                 top2++;
>                 strcpy(state2[top2],tpCode); 
>             }
>             tpCode[tpPos]++;   
>         }
>     }
>     stackStep2=top2;
>         
>     }    
> }    
> 
> 
> int main() {
>     code[0]='1';
>     final[0]='1';
>     scanf("%s %s",&code[1],&final[1]);
>     if(!strcmp(code,final)) printf("0");
>     else printf("%d",BfsDual(code,final,0));
>     system("pause");
>   return 0;
> }

Home Page Go Back To top

TL 哪位有时间帮我看看啊 谢谢

TL 哪位有时间帮我看看啊谢谢