從兩個方向分別擴展，效率果然好很多^_^
總算對雙廣有點了解了，再做點題應(yīng)該就會熟悉了吧
#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[])//讀入一組數(shù)據(jù)，返回值是這組數(shù)據(jù)中"1"的個數(shù)
{
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;
}
//交換一個狀態(tài)中第i列和第j列，i從0開始計
void Swap_Two_Row(int a[],int i,int j)
{
swap(a[i],a[j]);
}
//交換一個狀態(tài)中第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);
}
}
//反轉(zhuǎn)一個狀態(tài)中的第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));
}
}
//反轉(zhuǎn)一個狀態(tài)中的第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中已經(jīng)有這個狀態(tài)，返回
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的性質(zhì)，所以搜到的第一個解答即為答案
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中已經(jīng)有這個狀態(tài)，返回
Back_Hash[key]=p.step;
Back_Q.push(p);
it=Front_Hash.find(key);
if(it!=Front_Hash.end())//插入Back_Q后看看Front_Q中有沒有這個狀態(tài)，有就說明搜到了解
{
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隊首拿出的第一個結(jié)點，新擴展出來的節(jié)點
NODE Back_last,Back_now;//從Back_Q隊首拿出的第一個結(jié)點，新擴展出來的節(jié)點
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;
}