题目描述

在你的帮助下，Oliver终于追到小X了，可有一天，坏人把小X抓走了。这正是Oliver英雄救美的时候。所以，Oliver又找到哆啦A梦，借了一个机器，机器显示出一幅方格地图，它告诉Oliver哪里能走，哪里不能走,。并且Oliver在这个地图的右下角，而小X在左上角。时间紧急，Oliver想知道，最少要走多少个格子,才能找到小X。（只能直走）。

输入

共N+1行，第一行为N，以下N行N列0-1矩阵，1表示不能通过,0表示可以通过(左上角和右下角为0). N<30.

输出

共一个数，为最少的走的格子数.

思路

用bfs直接找到最短路径就可以了，只是空间会很大。。。。。。

const
  dx:array[1..4] of integer=(-1,0,1,0);
  dy:array[1..4] of integer=(0,1,0,-1);
var
  s,n,q1,q2,p2,p1:longint;
  state:array[1..1000000,1..2] of longint;
  father:array[1..1000000] of longint;
  a:array[0..10000,0..10000] of integer;

procedure init;
  var
    i,j,k:longint;
    x:char;
  begin
    readln(n);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            read(x);
            a[i,j]:=ord(x)-ord('0');
          end;
        readln;
      end;
    read(q1,q2,p1,p2);
end;

function check(x,y:longint):boolean;
  begin
    check:=true;
    if a[x,y]=1 then check:=false;
    if (x<1) or (y<1) or (x>n) or (y>n) then check:=false;
end;

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

procedure bfs;
  var
    head,tail,i:longint;
  begin
    head:=0;
    tail:=1;
    state[1,1]:=q1;
    state[1,2]:=q2;
    repeat
      inc(head);
      for i:=1 to 4 do
        if check(state[head,1]+dx[i],state[head,2]+dy[i]) then
          begin
            inc(tail);
            father[tail]:=head;
            state[tail,1]:=state[head,1]+dx[i];
            state[tail,2]:=state[head,2]+dy[i];
            a[state[tail,1],state[tail,2]]:=1;
            if (state[tail,1]=p1) and (state[tail,2]=p2) then
              begin
                print(tail);
                write(s-1);
                tail:=0;
              end;
          end;
    until head>=tail;
end;

begin
  init;
  bfs;
end.