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 阅读(486) 评论(1)  编辑 收藏 引用

评论

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

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


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理