黑白棋游戏 (codevs 2743)题解

【问题描述】

黑白棋游戏的棋盘由4×4方格阵列构成。棋盘的每一方格中放有1枚棋子,共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时,每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态,编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

【样例输入】

1111

0000

1110

0010

1010

0101

1010

0101

【样例输出】

4

1222

1424

3242

4344

【解题思路】

看到最少步数,果断广搜。不过状态太多,需要判重。大家可以看到,出题人在数据一栏写了必须用状态压缩,不能用康托展开和hash,他说往东走,咱们偏往西走,就用hash优化。(别想从我嘴里套出我不会状态压缩和康托展开)不过hash函数会很不好找,这里我用的是二进制转十进制的方法存hash,这样的话保证每种状态下只有一个hash函数,就不需要挂链表了,主要的是比较目前状态与目标状态是否相同时会耗费点时间,不过1s还是能过的,然后一个关键的地方就是存储哪两个坐标换了位置,我是用的字符来存的,详见代码。

【代码实现】

 type arr=array[..,..] of char;
rec=record
m:arr;
step:longint;
ans:array[..,..] of char;
end;
const dx:array[..] of longint=(,-,,);
dy:array[..] of longint=(,,-,);
var start,ans:rec;
f:array[..] of boolean;
spos,epos:arr;
fr,r,i,j:longint;
a:array[..] of rec;
function equal(m:arr):boolean;
var i,j:longint;
begin
for i:= to do
for j:= to do
if m[i,j]<>epos[i,j] then exit(false);
exit(true);
end;
function hash(m:arr):longint;//二进制转十进制,用位运算,效率高
var res,i,j:longint;
begin
res:=;
for i:= to do
for j:= to do
begin
res:=(res shl );
res:=res+ord(m[i,j])-ord('');
end;
exit(res);
end;
procedure bfs;
var t,i,j,k,x,y:longint;
now,next:rec;
temp:char;
begin
fillchar(f,sizeof(f),true);
t:=hash(spos);
f[t]:=false;
fr:=;r:=;
while fr<>r do
begin
inc(fr);
now:=a[fr];
if equal(now.m) then
begin
ans:=now;
exit;
end;
for i:= to do
for j:= to do
for k:= to do
begin
next:=now;
inc(next.step);
x:=i+dx[k];
y:=j+dy[k];
if (x>=)and(x<=)and(y>=)and(y<=) then
begin
temp:=next.m[i,j];
next.m[i,j]:=next.m[x,y];
next.m[x,y]:=temp;
next.ans[next.step,]:=chr(ord('')+i);
next.ans[next.step,]:=chr(ord('')+j);
next.ans[next.step,]:=chr(ord('')+x);
next.ans[next.step,]:=chr(ord('')+y);
next.ans[next.step,]:=#;//存储哪两个坐标换了位置
if equal(next.m) then
begin
ans:=next;
exit;
end;
t:=hash(next.m);
if f[t] then
begin
f[t]:=false;
inc(r);
a[r]:=next;
end;
end;
end;
end;
end;
begin
for i:= to do
begin
for j:= to do
read(spos[i,j]);
readln;
end;
for i:= to do
begin
for j:= to do
read(epos[i,j]);
readln;
end;
for i:= to do
for j:= to do
start.m[i,j]:=spos[i,j];
start.step:=;
a[]:=start;
bfs;
writeln(ans.step);
for i:= to ans.step do
begin
for j:= to do
write(ans.ans[i,j]);
writeln;
end;
end.
上一篇:Struts2 的 值栈和ActionContext


下一篇:php curl模拟post请求提交数据样例总结