| ||||||||||
| 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 | |||||||||
窝的丑AC代码#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct fuck{
char map[6][6];
int hash;
int step;
int last,bitch;
}f[100008];
struct shit{
int a,b,c,d;
}pf[100008],df[100008];
bool vis[200000];
int k,indek;
int dir[2][2]={0,1,1,0};
void fuckswap(char *a,char *b)
{
char t;
t=*a;
*a=*b;
*b=t;
}
int gethash(fuck h)
{
int i,j,bitch=1;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
bitch=bitch<<1;
if(h.map[i][j]=='1')
bitch=bitch|1;
}
return bitch;
}
int bfs()
{
int i,j,nx,ny,t,fuckbitch,fuckhash;
queue<fuck> q;
struct fuck g;
f[1].step=0;f[1].last=0;f[1].bitch=1;
vis[f[1].hash]=false;
q.push(f[1]);
while(!q.empty())
{
g=q.front();
fuckbitch=g.bitch;
fuckhash=g.hash;
q.pop();
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
for(t=0;t<2;t++)
{
nx=i+dir[t][0];
ny=j+dir[t][1];
if(nx<4&&ny<4&&g.map[nx][ny]!=g.map[i][j])
{
swap(g.map[nx][ny],g.map[i][j]);
g.hash=gethash(g);
if(vis[g.hash])
{
vis[g.hash]=false;
g.step=g.step+1;
++k;
g.last=g.bitch;
g.bitch=k;
q.push(g);
f[k]=g;
pf[k].a=i;pf[k].b=j;pf[k].c=nx;pf[k].d=ny;
if(g.hash==f[0].hash)
return g.step;
g.step=g.step-1;
g.bitch=fuckbitch;
}
swap(g.map[nx][ny],g.map[i][j]);
}
}
}
}
return -1;
}
int main()
{
int i,j,sb;
memset(vis,true,sizeof(vis));
for(i=0;i<4;i++)
scanf("%s",f[1].map[i]);
getchar();
for(i=0;i<4;i++)
scanf("%s",f[0].map[i]);
f[0].hash=gethash(f[0]);f[1].hash=gethash(f[1]);
if(f[0].hash==f[1].hash)
printf("0\n");
else
{
k=1;indek=0;
printf("%d\n",bfs());
//printf("%d\n",k);
while(k>0)
{
//printf("%d %d %d %d\n",pf[k].a+1,pf[k].b+1,pf[k].c+1,pf[k].d+1);
//printf("%d\n",k);
df[indek++]=pf[k];
k=f[k].last;
}
for(i=indek-2;i>=0;i--)printf("%d %d %d %d\n",df[i].a+1,df[i].b+1,df[i].c+1,df[i].d+1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator