题解 P1605 【迷宫】

GEM_IU_077 · 2017-08-17 14:08:13 · 题解

dfs(大法师）pascal福利

此题是一道典型的深搜题目，将能通过的位置赋值为0，将不能通过的位置赋值为1，然后进行深度优先搜索就ok了。

千万别忘记原地回溯！！！不要将起点设为1,1！！！（如果一碰到障碍物或重点就返回（exit)）

下附代码：

  var
  i,j,k,n,m,t,sx,sy,fx,fy,a,b:longint;
  ans:int64;
  z:array[0..10,0..10] of longint;
  flag:array[0..10,0..10] of boolean;

procedure dfs(x,y:longint);   //深搜开始
  begin
    if z[x,y]=1 then exit;   //判断是否遇到障碍物
    if (x=fx) and (y=fy)   //判断是否到达终点
      then
        begin
          inc(ans);   //更新答案
          exit;
        end;
    flag[x,y]:=true;  //将**flag[x,y]**设为已经走过
    if (x-1>0) and (not flag[x-1,y]) then dfs(x-1,y);   //递归开始（如果越出地图或那一个点一走过则不进行深搜）
    if (x+1<=n) and (not flag[x+1,y]) then dfs(x+1,y);
    if (y-1>0) and (not flag[x,y-1])then dfs(x,y-1);
    if (y+1<=m) and (not flag[x,y+1])then dfs(x,y+1);
    flag[x,y]:=false;   //原地回溯
  end;

begin
  readln(n,m,t);
  readln(sx,sy,fx,fy);
  fillchar(z,sizeof(z),0);
  for i:=1 to t do
    begin
      readln(a,b);
      z[a,b]:=1;
    end;
  dfs(sx,sy);   //调用子程序
  writeln(ans);   //输出（大功告成）
end.

z[x,y]表示此点是否可通行，flag[x,y]表示此点是否走过