| ||||||||||
| 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 | |||||||||
唉,为什么我的怎么慢啊:(#include<iostream>
#include<algorithm>
using namespace std;
#define max 65536
struct node
{
bool map[4][4];
int step;
}q[max*2];
int visit[max],tar1=0,tar2=max-1;
int pow2[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
/*void init()
{
int m=1;
for(int i=0;i<16;i++)
{
pow2[i]=m;
m*=2;
}
}*/
int trans(bool a[4][4])
{
int m=0;
for(int i=0;i<16;i++)
{
m=m+a[i/4][i%4]*pow2[i];
}
return m;
}
int bfs(node s)
{
int h=0,t=1;
q[h]=s;
q[h].step=0;
visit[trans(s.map)]=1;
node cur,next;
while(h<t)
{
cur=q[h];
if(trans(cur.map)==tar1||trans(cur.map)==tar2)
{
return cur.step;
}
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
next=cur;
if(i>0)
{
next.map[i-1][j]=!cur.map[i-1][j];
}
if(i<3)
{
next.map[i+1][j]=!cur.map[i+1][j];
}
if(j>0)
{
next.map[i][j-1]=!cur.map[i][j-1];
}
if(j<3)
{
next.map[i][j+1]=!cur.map[i][j+1];
}
next.map[i][j]=!cur.map[i][j];
if(!visit[trans(next.map)])
{
next.step=cur.step+1;
q[t++]=next;
visit[trans(next.map)]=1;
}
}
}
h++;
}
return -1;
}
int main()
{
// init();
node cur;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
char c;
cin>>c;
c=='w'?cur.map[i][j]=1:cur.map[i][j]=0;
}
}
memset(visit,0,sizeof(visit));
int k;
k=bfs(cur);
if(k==-1)
{
cout<<"Impossible"<<endl;
}
else
{
cout<<k<<endl;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator