The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

暑假集訓專題訓練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 閱讀(520) 評論(1) 編輯收藏引用

# re: 暑假集訓專題訓練1::搜索行列轉換問題初識雙向廣搜[未登錄] 2011-04-30 21:56 clover

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

暑假集訓專題訓練1::搜索行列轉換問題初識雙向廣搜

評論

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

暑假集訓專題訓練1::搜索 行列轉換問題 初識雙向廣搜

評論

# re: 暑假集訓專題訓練1::搜索 行列轉換問題 初識雙向廣搜[未登錄] 2011-04-30 21:56 clover

暑假集訓專題訓練1::搜索行列轉換問題初識雙向廣搜

# re: 暑假集訓專題訓練1::搜索行列轉換問題初識雙向廣搜[未登錄] 2011-04-30 21:56 clover