Nguồn đề bài: CHESSCBG
1. Đề bài CHESSCBG spoj
Một bàn cờ thế là một bảng gồm 4 dòng, 4 cột. Mỗi thế cờ là một cách sắp xếp 8 quân cờ, hai quân khác nhau ở hai ô khác nhau. Bài toán đặt ra là cho hai thế cờ 1 và 2, hãy tìm một số ít nhất bước di chuyển quân để chuyển từ thế 1 sang thế 2; một bước di chuyển quân là một lần chuyển quân cờ sang ô trống kề cạnh với ô quân cờ đang đứng.
Dữ liệu vào
Từ file văn bản gồm 8 dòng, mỗi dòng là một xâu nhị phân độ dài 4 mà số 1/0 tương ứng với vị trí có hoặc không có quân cờ. Bốn dòng đầu là thế cờ 1, bốn dòng sau là thế cờ 2.
Dữ liệu ra
Gồm 1 dòng duy nhất là số bước chuyển quân ít nhất
Ví dụ
Dữ liệu vào:
1111
0000
1110
0010
1010
0101
1010
0101
Dữ liệu ra :
4
2. Code tham khảo CHESSCBG spoj
Pascal
const fi='';
H:array[1..4] of longint=(-1,4,-4,1);
maxbit=66000;
type
data=word;
var
f:text;
x,y:data;
Q:array[0..maxbit] of data;
C:array[0..maxbit] of data;
sd:array[1..16] of data;
D:array[1..16,1..4] of data;
dau,cuoi:data;
function getbit(k,x:data):byte;
begin
getbit:=(x shr (k-1)) and 1;
end;
procedure Setbit(c,k:byte; var x:data);
begin
if c=1 then
x:=x or (1 shl (k-1))
else
x:=x and (not (1 shl (k-1)));
end;
procedure docfile;
var i,j:data;
c:char;
begin
assign(f,fi); reset(f);
x:=0;
y:=0;
for i:=1 to 16 do
begin
read(f,c);
if c='1' then
setbit(1,i,x);
if i mod 4 = 0 then
readln(f);
end;
for i:=1 to 16 do
begin
read(f,c);
if c='1' then
setbit(1,i,y);
if i mod 4 = 0 then
readln(f);
end;
close(f);
end;
procedure init;
var i,j,dau,cuoi:data;
tinh:integer;
begin
fillchar(sd,sizeof(sd),0);
fillchar(d,sizeof(d),0);
for i:=1 to 16 do
begin
dau:=1;
cuoi:=4;
if i and 3 = 1 then
dau:=2
else
if i and 3 = 0 then
cuoi:=3;
for j:=dau to cuoi do
begin
tinh:=i+h[j];
if tinh in [1..16] then
begin
inc(sd[i]);
d[i,sd[i]]:=tinh;
end;
end;
end;
end;
procedure themvao(x,y:data);
begin
inc(cuoi);
Q[cuoi]:=x;
c[x]:=y;
end;
function layra:data;
begin
layra:=q[dau];
inc(dau);
end;
Function gt(x,i: data):data;
Begin
if GetBit(i,x)=1 then
exit(254);
gt:=x;
SetBit(1,i,gt);
End;
procedure bfs;
var i,j,bit,tt:data;
tinh:data;
begin
init;
dau:=1;
cuoi:=0;
fillchar(c,sizeof(c),0);
C[254]:=100;
themvao(x,1);
while (dau<=cuoi) do
begin
bit:=layra;
tt:=c[bit]+1;
for i:=1 to 16 do
if getbit(i,bit)=1 then
begin
setbit(0,i,bit);
for j:=1 to sd[i] do
begin
tinh:=gt(bit,d[i,j]);
if c[tinh]=0 then
begin
themvao(tinh,tt);
if c[y]<>0 then
exit;
end;
end;
setbit(1,i,bit);
end;
end;
end;
begin
docfile;
bfs;
writeln(c[y]-1);
end.
C++
#include <bits/stdc++.h>
using namespace std;
int Start, End;
int first, last;
vector<int> Visit,d,mu2;
queue<int> que;
void Init()
{
ios_base::sync_with_stdio(false);
mu2.resize(50);
mu2[16]=1;
for (int i=15;i>0;i--)
{
mu2[i]=mu2[i+1]*2;
}
char tg;
for (int i=1;i<=16;i++)
{
cin>>tg;
if(tg=='1') Start+=mu2[i];
}
for (int i=1;i<=16;i++)
{
cin>>tg;
if(tg=='1') End+=mu2[i];
}
Visit.resize(mu2[1]*2+2);
d.resize(mu2[1]*2+2);
}
void TryLeft(int u, int i)
{
int v=u-mu2[i]+mu2[i-1];
if(!Visit[v])
{
que.push(v);
d[v]=d[u]+1;
Visit[v]=true;
}
}
void TryRight(int u, int i)
{
int v=u-mu2[i]+mu2[i+1];
if(!Visit[v])
{
que.push(v);
d[v]=d[u]+1;
Visit[v]=true;
}
}
void TryUp(int u, int i)
{
int v=u-mu2[i]+mu2[i-4];
if(!Visit[v])
{
que.push(v);
d[v]=d[u]+1;
Visit[v]=true;
}
}
void TryDown(int u, int i)
{
int v=u-mu2[i]+mu2[i+4];
if(!Visit[v])
{
que.push(v);
d[v]=d[u]+1;
Visit[v]=true;
}
}
void Solve()
{
que.push(Start);
Visit[Start]=true;
while (!que.empty())
{
int u=que.front();
que.pop();
if(u==End)
{
cout<<d[End];
return;
}
for (int i=1;i<=16;i++)
{
if((u&mu2[i])!=0)
{
if(i%4!=1 && (u&mu2[i-1])==0)
TryLeft(u,i);
if(i%4!=0 && (u&mu2[i+1])==0)
TryRight(u,i);
if(i>4 && (u&mu2[i-4])==0)
TryUp(u,i);
if(i<13 && (u&mu2[i+4])==0)
TryDown(u,i);
}
}
}
}
int main()
{
Init();
Solve();
}
