CHESSCBG spoj - Bàn cờ thế

Nguồn đề bài: CHESSCBG

Nội dung bài viết

1. Đề bài CHESSCBG spoj
2. Code tham khảo CHESSCBG spoj
- Pascal
- C++

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.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

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;

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;

setbit(1,i,bit);

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();
}

100

101

102

103

104

105

106

107

108

109

110

111

#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();

}

CHESSCBG spoj – Bàn cờ thế

1. Đề bài CHESSCBG spoj

Dữ liệu vào

Dữ liệu ra

Ví dụ

2. Code tham khảo CHESSCBG spoj

Pascal

C++

Bài viết liên quan

Trả lời Hủy