SSL JudgeOnline 1456——骑士旅行

问题描述：
在一个n m 格子的棋盘上，有一只国际象棋的骑士在棋盘的左下角 (1;1)(如图1)，骑士只能根据象棋的规则进行移动，要么横向跳动一格纵向跳动两格，要么纵向跳动一格横向跳动两格。 例如， n=4，m=3 时，若骑士在格子(2;1) (如图2), 则骑士只能移入下面格子：(1;3),(3;3) 或 (4;2)；对于给定正整数n，m，I，j值 (m,n<=50,I<=n,j<=m) ，你要测算出从初始位置(1;1) 到格子(i;j)最少需要多少次移动。如果不可能到达目标位置，则输出”NEVAR”。

输入文件(Horse.in)：
输入文件的第一行为两个整数n与m，第二行为两个整数i与j。
输出文件(Horse.out)：
输出文件仅包含一个整数为初始位置(1;1) 到格子(i;j)最少移动次数。
样例输入
Horse.in
5 3
1 2

---

这题也是一道广搜题

我们每次搜马走的八个方向，判断如走这个点有没有越界，在判断这个点有没有被走过，如果走过，这个点已经有了最短路径。最后如果已经搜到了终点，直接输出，因为广搜搜到的每一个点都是最短路径。

---

代码如下：

const dx:array[1..8]of longint=(2,2,1,1,-1,-1,-2,-2);
      dy:array[1..8]of longint=(1,-1,-2,2,-2,2,1,-1);

var  total,n,m,i,j,qx,qy,l:longint;
     a:array[-5..101,-5..101]of 0..1;
     father:array[-5..10001]of longint;
     state:array[-5..10001,1..3]of longint;
     s:string;

procedure print(x:longint);
begin
  if x=0 then exit;
  inc(l);
  print(father[x]);
end;

procedure bfs;
var  head,tail,x,y,i:longint;
begin
  head:=0; tail:=1; state[1,1]:=1; state[1,2]:=1; state[1,3]:=0;
  father[1]:=0;
  repeat
    inc(head);
    for i:=1 to 8 do
      begin
        x:=state[head,1]+dx[i];
        y:=state[head,2]+dy[i];
        if (x>0)and(x<=m)and(y>0)and(y<=n)and(a[x,y]=0) then
          begin
            inc(tail);
            father[tail]:=head;
            state[tail,1]:=x;
            state[tail,2]:=y;
            a[x,y]:=1;
            state[tail,3]:=state[head,3]+1;
            if (x=qx)and(y=qy) then
              begin
                total:=tail;
                exit;
              end;
          end;
      end;
  until head>=tail;
end;

begin
  fillchar(a,sizeof(a),#0);
  readln(n,m);
  read(qx,qy);
  bfs;
  if total=0 then writeln('NEVER')
             else writeln(state[total,3]);
end.