| ||||||||||
| 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 | |||||||||
麻烦哪位大牛也好 小牛也好 帮忙看一下我的BFS+位运算为什么超时 谢谢#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=70000;
int a[6][6]={0};
int change[5][5]={{0},{0,0xf888,0xf444,0xf222,0xf111},{0,0x8f88,0x4f44,0x2f22,0x1f11},{0,0x88f8,0x44f4,0x22f2,0x11f1},{0,0x888f,0x444f,0x222f,0x111f}};
int que[700000];
int pre[N]={0},c[N],r[N],step[N];
int flag[N]={0};
int ans1[N],ans2[N];
int main()
{
//freopen("data.in.txt","r",stdin);
int i,j;
int k=0;
char d;
for(i=1;i<=4;i++)
{
for(j=1;j<=4;j++)
{
scanf("%c",&d);
if(d=='+')
k+=1<<(16-(i-1)*4-j);
}
getchar();
}
int p=0,q=0,t,state;
que[p++]=k;
pre[k]=-1;
while(q<=p)
{
t=que[q];
if(t==0)
break;
if(flag[t]==0)
{
flag[t]=1;
for(i=1;i<=4;i++){
for(j=1;j<=4;j++)
{
state=t^change[i][j];
if(!flag[state])
{
que[p++]=state;
pre[state]=t;
r[state]=i;
c[state]=j;
step[state]=step[t]+1;
if(state==0)
break;
}
}
if(state==0)
break;
}
if(state==0)
break;
}
q++;
}
cout<<step[0]<<endl;
t=0;
for(i=1;i<=step[0];i++)
{
ans1[i]=r[t];
ans2[i]=c[t];
t=pre[t];
}
for(i=1;i<=step[0];i++)
cout<<ans1[i]<<" "<<ans2[i]<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator