CHESSCBG - Bàn cờ thế
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<int> vi;
int s[65546][19];
vi e[65546];
int val;
bool c[7][7];
int v[7][7];
ii x[9];
int df[4]={-1,0,1,0};
int ds[4]={0,-1,0,1};
int vs,vf;
int col[65546];
int lev[65546];
void btrk(int k)
{
int i,j,t;
for (i=x[k-1].first;i<=4;i=i+1)
for (j=1;j<=4;j=j+1)
{
if (i<x[k-1].first) continue;
if ((i==x[k-1].first) && (j<=x[k-1].second)) continue;
if (c[i][j])
{
x[k]=ii(i,j);
c[i][j]=false;
val=val+v[i][j];
if (k==8)
{
for (t=1;t<=8;t=t+1)
{
s[val][2*t-1]=x[t].first;
s[val][2*t]=x[t].second;
}
col[val]=0;
}
else btrk(k+1);
c[i][j]=true;
val=val-v[i][j];
}
}
}
void gen_verticles(void)
{
int i,j;
int z=1;
memset(col,3,sizeof col);
memset(lev,0,sizeof lev);
for (i=4;i>=1;i=i-1)
for (j=4;j>=1;j=j-1)
{
v[i][j]=z;
z=z*2;
c[i][j]=true;
}
val=0;
btrk(1);
}
void gen_edge(void)
{
bool cl[7][7];
int i,j,k;
for (i=0;i<=5;i=i+1)
{
cl[0][i]=false;
cl[i][0]=false;
cl[5][i]=false;
cl[i][5]=false;
}
for (i=0;i<=65540;i=i+1)
{
if (col[i]>0) continue;
for (j=1;j<=4;j=j+1)
for (k=1;k<=4;k=k+1)
cl[j][k]=true;
for (j=1;j<=8;j=j+1)
cl[s[i][2*j-1]][s[i][2*j]]=false;
for (j=1;j<=8;j=j+1)
for (k=0;k<=3;k=k+1)
if (cl[s[i][2*j-1]+df[k]][s[i][2*j]+ds[k]])
e[i].push_back(i-v[s[i][2*j-1]][s[i][2*j]]+v[s[i][2*j-1]+df[k]][s[i][2*j]+ds[k]]);
}
}
void getdata(void)
{
int i,j,k;
char s[10];
vs=0;
for (i=1;i<=4;i=i+1)
{
scanf("%s",s);
for (j=1;j<=4;j=j+1)
if (s[j-1]==49) vs=vs+v[i][j];
}
vf=0;
for (i=1;i<=4;i=i+1)
{
scanf("%s",s);
for (j=1;j<=4;j=j+1)
if (s[j-1]==49) vf=vf+v[i][j];
}
col[vs]=1;
}
void bfs(void)
{
int i;
queue<int> q;
q.push(vs);
col[vs]=1;
lev[vs]=0;
while (!q.empty())
{
int x=q.front();
q.pop();
if (col[vf]>0)
{
printf("%d",lev[vf]);
return;
}
for (i=0;i<e[x].size();i=i+1)
{
if (col[e[x][i]]==0)
{
q.push(e[x][i]);
col[e[x][i]]=1;
lev[e[x][i]]=lev[x]+1;
}
}
}
}
int main(void)
{
gen_verticles();
gen_edge();
getdata();
bfs();
}