题目:多多下棋 rqnoj220
题目描述
【问题描述】
多多经常和叔叔下中国象棋，叔叔每次都赢，多多很不服气，今天她又找叔叔和他下象棋。。。。。。。。。
下到最后，多多只有一匹“马”可以用来进攻，而叔叔只有“将”，所有可以用来进攻和防御的棋子都被多多“吃” 了。（显然今天多多RP暴发）在一个给定的棋局下（将一定在棋盘第一行的中央），多多怎么走能在叔叔不移动“将”的情况下尽快赢了。
【数据范围】
棋盘是标准的中国象棋棋盘（10*9）；
马的在象棋盘内；
【时限】
1S
注：在移动过程中“马”不能被“将”吃掉。（如果马走到（1，4），（1，6），（2，5））这三个点就被“将”吃掉了。
输入数据保证合理。
在象棋中马走日的规矩大家都知道吧！！
输入格式
只有一行，两个用空格隔开的数X Y。表示“马”在象棋盘中的位置
（X行Y列），规定“将”所在位置为1行中央，即：（1，5）点。
输出格式
只有一个数，多多要赢所走的最少的步数。（叔叔的“将”不移动位置）。
如果多无法赢了叔叔则输出“No Answer” (不包含“”号) 。
样例输入
样例输出
宽搜吧。。。应该不难
program rqnoj220;
const
dx:array[1..8] of longint=( 1, 1,-1,-1, 2, 2,-2,-2);
dy:array[1..8] of longint=( 2,-2, 2,-2, 1,-1, 1,-1);
type
tnode=record
x,y,step:longint;
end;
var
first,target:tnode;
l,r:longint;
q:array[0..10*9*10*9+100] of tnode;
h:array[0..20,0..20] of boolean;
procedure init;
begin
assign(input,'rqnoj220.in');
assign(output,'rqnoj220.out');
reset(input);
rewrite(output);
end;
procedure outit;
begin
close(input);
close(output);
halt;
end;
procedure readdata;
begin
read(first.x,first.y);
first.step:=-1;//入队后 +1 为 0
target.x:=1;
target.y:=5;
end;
function isok(x,y:longint):boolean;
begin
if ((x=1)and(y=4))and((x=1)and(y=6))and((x=2)and(y=5)) then exit(false);
exit(true);
end;
procedure inq(var x:tnode);
begin
inc(r);
inc(x.step);
h[x.x,x.y]:=true;
if (x.x=target.x)and(x.y=target.y) then
begin
writeln(x.step);
outit;
end;
q[r]:=x;
end;
function outq:tnode;
begin
inc(l);
exit(q[l]);
end;
procedure kuo(var node,newnode:tnode;i:longint);
begin
newnode:=node;
newnode.x:=newnode.x+dx[i];
newnode.y:=newnode.y+dy[i];
if not isok(newnode.x,newnode.y) then newnode:=node;
if (newnode.x<1)or(newnode.x>10)or(newnode.y<1)or(newnode.y>9) then newnode:=node;
end;
procedure main;
var
node,newnode:tnode;
i:longint;
begin
fillchar(h,sizeof(h),0);
inq(first);
while l<r do
begin
node:=outq;
for i:=1 to 8 do
begin
kuo(node,newnode,i);
if not h[newnode.x,newnode.y] then inq(newnode);
end;
end;
writeln('No Answer');
end;
begin
init;
readdata;
main;
outit;
end.
