题解 P1605 【迷宫】

GEM_IU_077

2017-08-17 14:08:13

Solution

###dfs(大法师)pascal福利 此题是一道典型的深搜题目,将能通过的位置赋值为0,将不能通过的位置赋值为1,然后进行深度优先搜索就ok了。 ###千万别忘记原地回溯!!!不要将起点设为1,1!!!(如果一碰到障碍物或重点就返回(exit)) 下附代码: ```pas 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]**表示此点是否走过