The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

暑假集训专题训练1::搜索 行列转换问题 初识双向广搜

从两个方向分别扩展,效率果然好很多^_^
总算对双广有点了解了,再做点题应该就会熟悉了吧
#include<iostream>
#include
<algorithm>
#include
<map>
#include
<queue>
using namespace std;

bool can;
int m,n,ans;


struct KEY
{
    
int a[10];
    
bool operator <(KEY o) const
    
{
        
for(int i=0;i<m;i++
            
if(a[i]!=o.a[i]) return a[i]<o.a[i];
        
return false;
    }

}
;


struct NODE
{
    
int a[10];
    
int step;
}
;

KEY key;
NODE s,t;
map
<KEY,int>Front_Hash,Back_Hash;
map
<KEY,int>::iterator it;
queue
<NODE>Front_Q,Back_Q;


int input(int a[])//读入一组数据,返回值是这组数据中"1"的个数
{
    
int c;
    
int i,j,num=0;
    
for(i=0;i<m;i++)
    
{
        
for(j=0;j<n;j++)
        
{
            scanf(
"%1d",&c);
            num
+=c;
            a[i]
=(a[i]<<1)+c;
        }

    }

    
return num;
}



//交换一个状态中第i列和第j列,i从0开始计
void Swap_Two_Row(int a[],int i,int j)
{
    swap(a[i],a[j]);
}


//交换一个状态中第i列和第j列,i从0开始计,i>j
void Swap_Two_Colum(int a[],int i,int j)
{
    
int k,p=1<<(n-j-1),q=1<<(n-i-1),r=i-j,x,y;
    
for(k=0;k<m;k++)
    
{
        x
=a[k]&p;
        y
=a[k]&q;
        a[k]
=a[k]-x-y+(x>>r)+(y<<r);
    }

}


//反转一个状态中的第i行
void Reverse_One_Row(int a[],int i)
{
    
int j,l=n>>1,x,y;
    
for(j=0;j<l;j++)
    
{
        x
=a[i]&(1<<(n-j-1));
        y
=a[i]&(1<<(j));
        a[i]
=a[i]-x-y+(x>>(n-j-j-1))+(y<<(n-j-j-1));
    }

}


//反转一个状态中的第i列
void Reverse_One_Colum(int a[],int i)
{
    
short j,l=m>>1,r=1<<(n-i-1),x,y;
    
for(j=0;j<l;j++)
    
{
        x
=a[j]&r;
        y
=a[m-j-1]&r;
        a[j]
=a[j]-x+y;
        a[m
-j-1]=a[m-j-1]-y+x;
    }
        
}


void Insert_Front_Queue(NODE p)
{
    
for(short i=0;i<m;i++)
        key.a[i]
=p.a[i];
    it
=Front_Hash.find(key);
    
if(it!=Front_Hash.end()) 
        
return;
    
//在Front_Q中已经有这个状态,返回
    Front_Hash[key]=p.step;
    Front_Q.push(p);
    it
=Back_Hash.find(key);
    
if(it!=Back_Hash.end())
    
{
        ans
=(p.step+it->second);//因为两个方向均满足BFS的性质,所以搜到的第一个解答即为答案
        can=true;
    }

}



void Insert_Back_Queue(NODE p)
{
    
for(int i=0;i<m;i++)
        key.a[i]
=p.a[i];
    it
=Back_Hash.find(key);
    
if(it!=Back_Hash.end()) 
        
return;
    
//在Back_Q中已经有这个状态,返回
    Back_Hash[key]=p.step;
    Back_Q.push(p);
    it
=Front_Hash.find(key);
    
if(it!=Front_Hash.end())//插入Back_Q后看看Front_Q中有没有这个状态,有就说明搜到了解
    {
        ans
=(it->second+p.step);//搜到的第一个解即为答案
        can=true;
    }

}


bool Equal(int a[],int b[])
{
    
for(short i=0;i<m;i++if(a[i]!=b[i]) return false;
    
return true;
}


void DBFS()//双向广搜主过程
{
    NODE Front_last,Front_now;
//从Front_Q队首拿出的第一个结点,新扩展出来的节点
    NODE Back_last,Back_now;//从Back_Q队首拿出的第一个结点,新扩展出来的节点
    while(!Front_Q.empty()) Front_Q.pop();
    
while(!Back_Q.empty()) Back_Q.pop();
    Front_Hash.clear();
    Back_Hash.clear();
    
//
    for(short i=0;i<m;i++) key.a[i]=s.a[i];
    Front_Hash[key]
=0;
    Front_Q.push(s);
    
//
    for(short i=0;i<m;i++) key.a[i]=t.a[i];
    Back_Hash[key]
=0;
    Back_Q.push(t);
    
//init
    while(!Front_Q.empty()||!Back_Q.empty())
    
{
        
int step;
        
if(!Front_Q.empty())//扩展正队列向
        {
            step
=Front_Q.front().step;
            
while(!Front_Q.empty()&&Front_Q.front().step==step)//一次扩展一层,注意这个Front_Q.front().step==step
            {
                Front_last
=Front_Q.front();
                
for(int i=0;i<m;i++)
                
{
                    
for(int j=0;j<i;j++)
                    
{
                        Front_now
=Front_last;
                        Swap_Two_Row(Front_now.a,i,j);
                        Front_now.step
++;    
                        Insert_Front_Queue(Front_now);
                        
if(can) return;
                    }

                    Front_now
=Front_last;
                    Reverse_One_Row(Front_now.a,i);
                    Front_now.step
++;
                    Insert_Front_Queue(Front_now);
                    
if(can) return;
                }

                
for(short i=0;i<n;i++)
                
{
                    
for(short j=0;j<i;j++)
                    
{
                        Front_now
=Front_last;
                        Swap_Two_Colum(Front_now.a,i,j);
                        Front_now.step
++;        
                        Insert_Front_Queue(Front_now);
                        
if(can) return;
                    }

                    Front_now
=Front_last;
                    Reverse_One_Colum(Front_now.a,i);
                    Front_now.step
++;
                    Insert_Front_Queue(Front_now);
                    
if(can) return;
                }

                Front_Q.pop();
                
if(can) return;
            }

        }

        
if(!Back_Q.empty())//扩展反向队列
        {
            step
=Back_Q.front().step;
            
while(!Back_Q.empty()&&Back_Q.front().step==step)//一层一层扩展
            {
                Back_last
=Back_Q.front();
                
for(short i=0;i<m;i++)
                
{
                    
for(short j=0;j<i;j++)
                    
{
                        Back_now
=Back_last;
                        Swap_Two_Row(Back_now.a,i,j);
                        Back_now.step
++;        
                        Insert_Back_Queue(Back_now);
                        
if(can) return;
                    }

                    Back_now
=Back_last;
                    Reverse_One_Row(Back_now.a,i);
                    Back_now.step
++;
                    Insert_Back_Queue(Back_now);
                    
if(can) return;
                }

                
for(short i=0;i<n;i++)
                
{
                    
for(short j=0;j<i;j++)
                    
{
                        Back_now
=Back_last;
                        Swap_Two_Colum(Back_now.a,i,j);
                        Back_now.step
++;    
                        Insert_Back_Queue(Back_now);
                        
if(can) return;
                    }

                    Back_now
=Back_last;
                    Reverse_One_Colum(Back_now.a,i);
                    Back_now.step
++;
                    Insert_Back_Queue(Back_now);
                    
if(can) return;
                }

                Back_Q.pop();
                
if(can) return;
            }

        }

    }

}


int main()
{
    
while(scanf("%d %d",&m,&n)!=EOF)
    
{
        
for(short i=0;i<m;i++) s.a[i]=t.a[i]=0;
        
int cnt1=0;
        
int cnt2=0;
        cnt1
=input(s.a);
        cnt2
=input(t.a);
        
if(cnt1!=cnt2)
        
{
            printf(
"No solution!\n");
            
continue;
        }

        s.step
=t.step=0;
        
if(Equal(s.a,t.a))
        
{
            puts(
"0");
            
continue;
        }

        can
=false;
        ans
=-1;
        DBFS();
        
if(can) 
            printf(
"%d\n",ans);
        
else
            puts(
"No solution!");
    }

    
return 0;
}





posted on 2010-07-10 22:42 abilitytao 阅读(404) 评论(1)  编辑 收藏 引用

评论

# re: 暑假集训专题训练1::搜索 行列转换问题 初识双向广搜[未登录] 2011-04-30 21:56 clover

还初识,这么长啊。怎么学  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理