题解 P2199 【最后的迷宫】

嚯呀嚯呀 · 2018-07-27 11:19:30 · 题解

P党福利！！！

这道题是一道搜索的水题，如果没有这个数据范围的话，估计都变成黄题了吧

对于100%的数据,有N*M<=16384

正常情况下为了防备出现极端情况(n=1,m=16384)，我们要把数组开到16500*16500，但是这样是不行了，会爆内存

于是乎我们用到了Pascal的动态数组

定义(在var下面写) a:array of longint; 这样我们就定义了一个一维的动态数组，只要在下面程序中写setlength(a,x)就可以开一个0到x-1的一维数组

二维数组的话map:array of array of longint;
setlength(map,n,m)就可以开一个0到n-1, 0到m-1的二维数组，多维的同理

这样的话，我们就可以根据n,m的大小动态的开数组，很方便哦

有一点要注意，动态数组无法用fillchar更新，会出现216错误(一般保护性错误)

再针对题目讲一点吧，我的做法是把能望到奖杯的位置先提前标记好，然后宽搜，只要走到标记过的位置就退出输出解(因为是宽搜，所以先得出来的解必定是最优解)

亮出我丑陋的代码，大佬们随便看看

var
  bi:boolean;
  ans,head,tail,a1,a2,xx,yy,x,y:longint;
  i,j,m,n,k,p:longint;
  map:array of array of char;
  check:array of array of longint;
  s:array[1..8]of longint=(-1,-1,0,1,1,1,0,-1);
  t:array[1..8]of longint=(0,1,1,1,0,-1,-1,-1);
  sx:array[1..4]of longint=(-1,0,1,0);
  sy:array[1..4]of longint=(0,1,0,-1);
  fx,fy,num:array[0..20000]of longint;
begin
  readln(n,m);
  setlength(map,n+1,m+1);
  setlength(check,n+1,m+1);
  for i:=1 to n do
    begin
      for j:=1 to m do
        read(map[i,j]);
      readln;
    end;
  while true do
    begin
      readln(xx,yy,x,y);
      if (xx=0)and(yy=0)and(x=0)and(y=0) then break;
      for i:=0 to n do
       for j:=0 to m do
         check[i,j]:=0;

      check[xx,yy]:=2;
      for i:=1 to 8 do
        if (xx+s[i]>=1)and(xx+s[i]<=n)and(yy+t[i]>=1)and
           (yy+t[i]<=m)and(map[xx+s[i],yy+t[i]]='O') then
          begin
            a1:=xx; a2:=yy;
            while (a1+s[i]>=1)and(a1+s[i]<=n)and(a2+t[i]>=1)and
                  (a2+t[i]<=m)and(map[a1+s[i],a2+t[i]]='O') do
              begin
                a1:=a1+s[i]; a2:=a2+t[i];
                check[a1,a2]:=2;
              end;
          end;
      {for i:=1 to n do
        begin
          for j:=1 to m do
            write(check[i,j]);
          writeln;
        end;}
      if check[x,y]=2 then
        begin
          writeln(0); continue;
        end;
      head:=0; tail:=1; fx[1]:=x; fy[1]:=y; num[1]:=0; check[x,y]:=1;
      bi:=false;
      while head<tail do
        begin
          inc(head);
          for i:=1 to 4 do
            if (fx[head]+sx[i]>=1)and(fx[head]+sx[i]<=n)and
               (fy[head]+sy[i]>=1)and(fy[head]+sy[i]<=m)and
               (check[fx[head]+sx[i],fy[head]+sy[i]]<>1)and
               (map[fx[head]+sx[i],fy[head]+sy[i]]='O')then
              begin
                if check[fx[head]+sx[i],fy[head]+sy[i]]=2 then
                  begin
                    ans:=num[head]+1; bi:=true; break;
                  end
                else
                  begin
                    inc(tail); fx[tail]:=fx[head]+sx[i];
                    fy[tail]:=fy[head]+sy[i]; num[tail]:=num[head]+1;
                    check[fx[tail],fy[tail]]:=1;
                  end;
              end;
          if bi=true then break;
        end;
      if bi=true then
        writeln(ans)
      else
        writeln('Poor Harry');
    end;
end.