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

双向BFS，调试一个星期了，就是不对啊，单向的两个方向的都对

Posted by 724548976 at 2009-09-30 20:04:05 on Problem 1077

#include<stdio.h>
#include<string.h>
#define N 365000
int fac[10]={1,2,6,24,120,720,5040,40320};
struct node
{
    int pos;//记录‘x’位置 
    int pre;//记录前一个操作 
    int flag;
    char state[10];//记录现在的状态 
};
char goal[10]="123456780";
node que[2][N],tmp,cur;
int flag[2][N],last[2];
int h[2],t[2];
void swap(char &c1,char &c2)
{
    char ch;
    ch=c1;c1=c2;c2=ch;
}
int change(char *c)
{
    int i,j,count,l,k;
    int s=0;l=strlen(c);
    int a[10];
    for(i=0;i<l;i++)
    if(c[i]=='0'){k=i;break;}
    for(i=0;i<k;i++)
    a[i]=c[i]-'0';
    for(i=k+1;i<l;i++)
    a[i-1]=c[i]-'0';
    a[i-1]=l-k-1;
    for(i=1;i<l-1;i++)
    {
        count=0;
        for(j=0;j<i;j++)
        if(a[i]<a[j])count++;
        s+=count*fac[i-1];
    }
    s+=fac[l-2]*a[l-1];
    return s;
}
int check(int i,int num)
{
   if(flag[1-i][num]==1)return 1;
   else return 0; 
}
void Sbfs()
{
        int num;
        cur=que[0][t[0]];
        if(cur.pos/3)//up 1
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos-3]);
            num=change(tmp.state);
            tmp.pos=cur.pos-3;
            if(check(0,num)) {last[0]=t[0];return;}
            if(!flag[0][num])
            {
               tmp.pre=t[0];
               tmp.flag=1;
               flag[0][num]=1;
               que[0][h[0]++]=tmp; 
            }
            
        }//if
        if(cur.pos/3!=2)//down 2
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos+3]);
            num=change(tmp.state);
            tmp.pos=cur.pos+3;
            if(check(0,num)) {last[0]=t[0];return;}
            if(!flag[0][num])
            {
               tmp.pre=t[0];
               tmp.flag=2;
               flag[0][num]=1;
               que[0][h[0]++]=tmp; 
            }
            
        }//if
        if(cur.pos%3)//left 3
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos-1]);
            num=change(tmp.state);
            tmp.pos=cur.pos-1;
             if(check(0,num)) {last[0]=t[0];return;}
            if(!flag[0][num])
            {
               tmp.pre=t[0];
               tmp.flag=3;
               flag[0][num]=1;
              que[0][h[0]++]=tmp; 
            }
            
        }//if
         if(cur.pos%3!=2)//right 4
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos+1]);
            num=change(tmp.state);
            tmp.pos=cur.pos+1;
            if(check(0,num)) {last[0]=t[0];return;}
            if(!flag[0][num])
            {
               tmp.pre=t[0];
               tmp.flag=4;
              flag[0][num]=1;
              que[0][h[0]++]=tmp; 
            }  
        }//if
    
}//Sbfs

void Ebfs()
{
        int num;
        cur=que[1][t[1]];
        if(cur.pos/3)//up 1
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos-3]);
            num=change(tmp.state);
            tmp.pos=cur.pos-3;
            //if(check(1,num)) {last[1]=t[1];return;}
            if(!flag[1][num])
            {
               tmp.pre=t[1];
               tmp.flag=1;
               flag[1][num]=1;
               que[1][h[1]++]=tmp; 
              if(check(1,num)) {last[1]=h[1]-1;return ;}
            }
            
        }//if
        if(cur.pos/3!=2)//down 2
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos+3]);
            num=change(tmp.state);
            
            tmp.pos=cur.pos+3;
             //if(check(1,num)){last[1]=t[1];return;}
            if(!flag[1][num])
            {
               tmp.pre=t[1];
               tmp.flag=2;
               flag[1][num]=1;
               que[1][h[1]++]=tmp; 
               if(check(1,num)) {last[1]=h[1]-1;return ;}
            }
            
        }//if
        if(cur.pos%3)//left 3
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos-1]);
            num=change(tmp.state);
            tmp.pos=cur.pos-1;
             //if(check(1,num)) {last[1]=t[1];return;}
            if(!flag[1][num])
            {
               tmp.pre=t[1];
               tmp.flag=3;
               flag[1][num]=1;
               que[1][h[1]++]=tmp; 
               if(check(1,num)) {last[1]=h[1]-1;return ;}
            }
            
        }//if
         if(cur.pos%3!=2)//right 4
        {
            tmp=cur;
            swap(tmp.state[cur.pos],tmp.state[cur.pos+1]);
            num=change(tmp.state);
            tmp.pos=cur.pos+1;
             //if(check(1,num)) {last[1]=t[1];return;}
            if(!flag[1][num])
            {
               tmp.pre=t[1];
               tmp.flag=4;
               flag[1][num]=1;
               que[1][h[1]++]=tmp; 
               if(check(1,num)) {last[1]=h[1]-1;return ;}
            }  
        }//if 
}//Ebfs

void Sprint(int t)
{
     if(que[0][t].pre==-1) return ;
     Sprint(que[0][t].pre);
     switch(que[0][t].flag)
    {
        case 1 :printf("u");break;
        case 2 :printf("d");break;
        case 3 :printf("l");break;
        case 4 :printf("r");break;        
    }

}
void Eprint(int t)
{
    while(que[1][t].pre!=-1)
    {
     switch(que[1][t].flag)
    {
        case 1 :printf("d");break;
        case 2 :printf("u");break;
        case 3 :printf("r");break;
        case 4 :printf("l");break;        
    }
    t=que[1][t].pre;
    }
}
int main()
{
    int i;
    char ch[2];
    while(scanf("%s",ch)!=EOF)
    {
        if(ch[0]=='x'){que[0][0].state[0]='0';que[0][0].pos=0;}
        else que[0][0].state[0]=ch[0];
        for(i=1;i<9;i++)
        {
              scanf("%s",ch);
              if(ch[0]=='x'){que[0][0].state[i]='0';que[0][0].pos=i;}
              else que[0][0].state[i]=ch[0];
        }
        que[0][0].state[i]=0; 
        que[0][0].pre=-1;
        strcpy(que[1][0].state,goal);
        que[1][0].pre=-1;
        que[1][0].pos=8;
        memset(flag,0,sizeof(flag));
        for(i=0;i<2;i++)
        last[i]=-1,h[i]=1,t[i]=0;
        while(t[0]<h[0]||t[1]<h[1])
        {
           if(last[0]==-1){Sbfs();t[0]++;}
           if(last[1]==-1){Ebfs();t[1]++;}
           if(last[1]!=-1&&last[0]!=-1)break;
        }
       if(last[0]!=-1||last[1]!=-1)
       {
            Sprint(last[0]);
            //printf("\n");
            Eprint(last[1]);
            printf("\n");
        }
       else printf("unsolvable\n");
    }   
}
/*

Sample Input

 2  3  4  1  5  x  7  6  8 
Sample Output

ullddrurdllurdruldr


*/

Followed by:

Re:双向BFS，调试一个星期了，就是不对啊，单向的两个方向的都对 (64) yayu_myself 2009-10-09 11:56:41

Post your reply here:

User ID:
Password:
Title:

Content:

> #include<stdio.h>
> #include<string.h>
> #define N 365000
> int fac[10]={1,2,6,24,120,720,5040,40320};
> struct node
> {
>     int pos;//记录‘x’位置 
>     int pre;//记录前一个操作 
>     int flag;
>     char state[10];//记录现在的状态 
> };
> char goal[10]="123456780";
> node que[2][N],tmp,cur;
> int flag[2][N],last[2];
> int h[2],t[2];
> void swap(char &c1,char &c2)
> {
>     char ch;
>     ch=c1;c1=c2;c2=ch;
> }
> int change(char *c)
> {
>     int i,j,count,l,k;
>     int s=0;l=strlen(c);
>     int a[10];
>     for(i=0;i<l;i++)
>     if(c[i]=='0'){k=i;break;}
>     for(i=0;i<k;i++)
>     a[i]=c[i]-'0';
>     for(i=k+1;i<l;i++)
>     a[i-1]=c[i]-'0';
>     a[i-1]=l-k-1;
>     for(i=1;i<l-1;i++)
>     {
>         count=0;
>         for(j=0;j<i;j++)
>         if(a[i]<a[j])count++;
>         s+=count*fac[i-1];
>     }
>     s+=fac[l-2]*a[l-1];
>     return s;
> }
> int check(int i,int num)
> {
>    if(flag[1-i][num]==1)return 1;
>    else return 0; 
> }
> void Sbfs()
> {
>         int num;
>         cur=que[0][t[0]];
>         if(cur.pos/3)//up 1
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos-3]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos-3;
>             if(check(0,num)) {last[0]=t[0];return;}
>             if(!flag[0][num])
>             {
>                tmp.pre=t[0];
>                tmp.flag=1;
>                flag[0][num]=1;
>                que[0][h[0]++]=tmp; 
>             }
>             
>         }//if
>         if(cur.pos/3!=2)//down 2
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos+3]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos+3;
>             if(check(0,num)) {last[0]=t[0];return;}
>             if(!flag[0][num])
>             {
>                tmp.pre=t[0];
>                tmp.flag=2;
>                flag[0][num]=1;
>                que[0][h[0]++]=tmp; 
>             }
>             
>         }//if
>         if(cur.pos%3)//left 3
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos-1]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos-1;
>              if(check(0,num)) {last[0]=t[0];return;}
>             if(!flag[0][num])
>             {
>                tmp.pre=t[0];
>                tmp.flag=3;
>                flag[0][num]=1;
>               que[0][h[0]++]=tmp; 
>             }
>             
>         }//if
>          if(cur.pos%3!=2)//right 4
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos+1]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos+1;
>             if(check(0,num)) {last[0]=t[0];return;}
>             if(!flag[0][num])
>             {
>                tmp.pre=t[0];
>                tmp.flag=4;
>               flag[0][num]=1;
>               que[0][h[0]++]=tmp; 
>             }  
>         }//if
>     
> }//Sbfs
> 
> void Ebfs()
> {
>         int num;
>         cur=que[1][t[1]];
>         if(cur.pos/3)//up 1
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos-3]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos-3;
>             //if(check(1,num)) {last[1]=t[1];return;}
>             if(!flag[1][num])
>             {
>                tmp.pre=t[1];
>                tmp.flag=1;
>                flag[1][num]=1;
>                que[1][h[1]++]=tmp; 
>               if(check(1,num)) {last[1]=h[1]-1;return ;}
>             }
>             
>         }//if
>         if(cur.pos/3!=2)//down 2
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos+3]);
>             num=change(tmp.state);
>             
>             tmp.pos=cur.pos+3;
>              //if(check(1,num)){last[1]=t[1];return;}
>             if(!flag[1][num])
>             {
>                tmp.pre=t[1];
>                tmp.flag=2;
>                flag[1][num]=1;
>                que[1][h[1]++]=tmp; 
>                if(check(1,num)) {last[1]=h[1]-1;return ;}
>             }
>             
>         }//if
>         if(cur.pos%3)//left 3
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos-1]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos-1;
>              //if(check(1,num)) {last[1]=t[1];return;}
>             if(!flag[1][num])
>             {
>                tmp.pre=t[1];
>                tmp.flag=3;
>                flag[1][num]=1;
>                que[1][h[1]++]=tmp; 
>                if(check(1,num)) {last[1]=h[1]-1;return ;}
>             }
>             
>         }//if
>          if(cur.pos%3!=2)//right 4
>         {
>             tmp=cur;
>             swap(tmp.state[cur.pos],tmp.state[cur.pos+1]);
>             num=change(tmp.state);
>             tmp.pos=cur.pos+1;
>              //if(check(1,num)) {last[1]=t[1];return;}
>             if(!flag[1][num])
>             {
>                tmp.pre=t[1];
>                tmp.flag=4;
>                flag[1][num]=1;
>                que[1][h[1]++]=tmp; 
>                if(check(1,num)) {last[1]=h[1]-1;return ;}
>             }  
>         }//if 
> }//Ebfs
> 
> void Sprint(int t)
> {
>      if(que[0][t].pre==-1) return ;
>      Sprint(que[0][t].pre);
>      switch(que[0][t].flag)
>     {
>         case 1 :printf("u");break;
>         case 2 :printf("d");break;
>         case 3 :printf("l");break;
>         case 4 :printf("r");break;        
>     }
> 
> }
> void Eprint(int t)
> {
>     while(que[1][t].pre!=-1)
>     {
>      switch(que[1][t].flag)
>     {
>         case 1 :printf("d");break;
>         case 2 :printf("u");break;
>         case 3 :printf("r");break;
>         case 4 :printf("l");break;        
>     }
>     t=que[1][t].pre;
>     }
> }
> int main()
> {
>     int i;
>     char ch[2];
>     while(scanf("%s",ch)!=EOF)
>     {
>         if(ch[0]=='x'){que[0][0].state[0]='0';que[0][0].pos=0;}
>         else que[0][0].state[0]=ch[0];
>         for(i=1;i<9;i++)
>         {
>               scanf("%s",ch);
>               if(ch[0]=='x'){que[0][0].state[i]='0';que[0][0].pos=i;}
>               else que[0][0].state[i]=ch[0];
>         }
>         que[0][0].state[i]=0; 
>         que[0][0].pre=-1;
>         strcpy(que[1][0].state,goal);
>         que[1][0].pre=-1;
>         que[1][0].pos=8;
>         memset(flag,0,sizeof(flag));
>         for(i=0;i<2;i++)
>         last[i]=-1,h[i]=1,t[i]=0;
>         while(t[0]<h[0]||t[1]<h[1])
>         {
>            if(last[0]==-1){Sbfs();t[0]++;}
>            if(last[1]==-1){Ebfs();t[1]++;}
>            if(last[1]!=-1&&last[0]!=-1)break;
>         }
>        if(last[0]!=-1||last[1]!=-1)
>        {
>             Sprint(last[0]);
>             //printf("\n");
>             Eprint(last[1]);
>             printf("\n");
>         }
>        else printf("unsolvable\n");
>     }   
> }
> /*
> 
> Sample Input
> 
>  2  3  4  1  5  x  7  6  8 
> Sample Output
> 
> ullddrurdllurdruldr
> 
> 
> */
>

Home Page Go Back To top