题解 P2802 【回家】

Z__X · 2018-06-23 21:25:25 · 题解

普及-的深搜题（不过其实我被坑了很多次）

这道题简单的说只要将坐标、时间、血量一直搜索，搜到边界，血量为零，此坐标有障碍物，或已经走过这个坐标，而如果碰到鼠标（怪异）则回满血（6），还有假如到家则判断最小值，dfs完输出就可以了

不说了，大家来看看本蒟蒻的代码吧：

var
  n,m,i,j,time_main:longint;
  a:array[0..10,0..10] of longint;
  b:array[0..10,0..10] of boolean;
procedure dfs(x,y,time,hp:longint);   //x和y分别表示行和列坐标，time表示时间，hp表示血量
begin
  dec(hp);                           //每走一格扣一点血
  if hp=0 then exit;                 //如果血量为0则退出
  if a[x,y]=0 then exit;             //如果此坐标是障碍物则退出
  if (x<1) or (x>n) or (y<1) or (y>m) then exit; //如果触碰边界则退出
  if b[x,y]=false then exit;         //如果此坐标已走过则退出
  if a[x,y]=4 then hp:=6;            //如果碰到鼠标则将血量回满
  if a[x,y]=3 then                   //如果到家则判断
    begin
      if time<time_main then time_main:=time; //比时间大小
      exit;
    end;
  b[x,y]:=false;                     //将走过的路标记
  dfs(x+1,y,time+1,hp);              //往下搜
  dfs(x-1,y,time+1,hp);              //往上搜
  dfs(x,y-1,time+1,hp);              //往左搜
  dfs(x,y+1,time+1,hp);              //往右搜
  b[x,y]:=true;                      //释放
end;
begin
  readln(n,m);
  fillchar(b,sizeof(b),true);
  for i:=1 to n do
   begin
     for j:=1 to m do read(a[i,j]);  //读入，应该不用说了
     readln;
   end;
  for i:=1 to n do
   for j:=1 to m do
    if a[i,j]=2 then
     begin
       time_main:=1000000000;       //存储时间最小值的变量
       dfs(i,j,0,6);                //开始神奇的dfs
       if time_main=1000000000 then write(-1)  //如果到不了家则输出‘-1’，否则输出最小值
       else write(time_main);
       halt;                       //结束程序
     end;
end.