题目:八数码难题 rqnoj70
题目描述
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入格式
输入初试状态，一行九个数字，空格用0表示
输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入
样例输出
这个游戏相信大家都应该玩过，然而这个题目的难点就是状态该怎么存，如何判断状态是否重复。。。。
这个就要用到康扩展开（可以自己百度）
接下来 就没什么难的了
Pascal Code
program rqnoj70;
const
dx:array[1..4] of longint=(0,0,1,-1);
dy:array[1..4] of longint=(1,-1,0,0);
type
tnode=record
node:array[1..3,1..3] of longint;
step:longint;
end;
var
l,r:longint;
q:array[0..1*2*3*4*5*6*7*8*9*9+10] of tnode;
h:array[0..1*2*3*4*5*6*7*8*9*9+10] of boolean;
first,target:tnode;
procedure init;
begin
assign(input,'rqnoj70.in');
assign(output,'rqnoj70.out');
reset(input);
rewrite(output);
end;
procedure outit;
begin
close(input);
close(output);
halt;
end;
procedure readdata;
var
i,j:longint;
ch:char;
begin
//初始化目标状态123804765
with target do
begin
node[1,1]:=1;
node[1,2]:=2;
node[1,3]:=3;
node[2,1]:=8;
node[2,2]:=0;
node[2,3]:=4;
node[3,1]:=7;
node[3,2]:=6;
node[3,3]:=5;
end;
//读入初始状态
for i:=1 to 3 do
for j:=1 to 3 do
begin
read(ch);
first.node[i,j]:=ord(ch)-ord('0');
end;
first.step:=-1;//入队后 +1 为 0
end;
function geth(x:tnode):longint;
var
a:array[0..8] of longint;
sum,num,i,j,k:longint;
begin
a[0]:=x.node[1,1];
a[1]:=x.node[1,2];
a[2]:=x.node[1,3];
a[3]:=x.node[2,1];
a[4]:=x.node[2,2];
a[5]:=x.node[2,3];
a[6]:=x.node[3,1];
a[7]:=x.node[3,2];
a[8]:=x.node[3,3];
sum:=0;k:=1;
for i:=1 to 8 do
begin
num:=0;
for j:=0 to i do
if a[j]<a[i] then
inc(num);
k:=k*i;
sum:=sum+num*k;
end;
exit(sum);
end;
procedure inq(var x:tnode);
begin
inc(r);
inc(x.step);
h[geth(x)]:=true;
q[r]:=x;
if geth(x)=geth(target) then
begin
writeln(x.step);
outit;
end;
end;
function outq:tnode;
begin
inc(l);
exit(q[l]);
end;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;a:=b;b:=t;
end;
procedure kuo(var node,newnode:tnode;x,y,i:longint);
var
newx,newy:longint;
begin
newnode:=node;
newx:=x+dx[i];
newy:=y+dy[i];
if (newx<1)or(newx>3)or(newy<1)or(newy>3) then exit;
swap(newnode.node[x,y],newnode.node[newx,newy]);
end;
procedure main;
var
i,j,k:longint;
node,newnode:tnode;
begin
inq(first);
while l<r do
begin
node:=outq;
for i:=1 to 3 do
for j:=1 to 3 do
if node.node[i,j]=0 then
for k:=1 to 4 do
begin
kuo(node,newnode,i,j,k);
if not h[geth(newnode)] then inq(newnode);
end;
end;
end;
begin
init;
readdata;
main;
outit;
end.
