P1363 幻想迷宫

本文主要是介绍P1363 幻想迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题可谓有好多解法，既然讲究效率，我还是选择了bfs。
bfs比较难下手，但理解题目后感觉还是挺简单的。
思路现将地图扩展成四份。

O=>OOOO

如果超过边界则到对应边的对应位置。
代码：

const z:array[1..4,1..2]of -1..1=((-1,0),(0,-1),(1,0),(0,1));
var i,j,k:longint;m,n,h,t:longint;fx,fy:longint;a:array[0..3001,0..3001]of 1..3;x,y:array[0..9000000]of longint;ch:char;
procedure add(x,y,p:longint);//扩张
begina[x,y]:=p;a[x,y+n]:=p;a[x+m,y]:=p;a[x+m,y+n]:=p;
end;
function pdx(x:longint):longint;//判断地图实际坐标
beginif x=0 then exit(m*2);if x=m*2+1 then exit(1);exit(x);
end;
function pdy(y:longint):longint;//判断地图实际坐标
beginif y=0 then exit(n*2);if y=n*2+1 then exit(1);exit(y);
end;
beginwhile not eof dobeginm:=0;n:=0;readln(m,n);if(m=0) and (n=0) then exit;//坑人的回车键for i:=1 to m dobeginfor j:=1 to n dobeginread(ch);if ch='S' then beginfx:=i;fy:=j;add(i,j,1);end;if ch='.' then add(i,j,2);if ch='#' then add(i,j,3);end;readln;end;for i:=1 to m*2 do//打上边界begina[i,0]:=3;a[i,n*2+1]:=3;end;for i:=1 to n*2 do//打上边界begina[0,i]:=3;a[m*2+1,i]:=3;end;h:=1;t:=1;k:=0;a[fx,fy]:=3;x[1]:=fx;y[1]:=fy;repeat//bfsfor i:=1 to 4 doif a[pdx(x[t]+z[i,1]),pdy(y[t]+z[i,2])]<>3 thenbegininc(h);x[h]:=pdx(x[t]+z[i,1]);y[h]:=pdy(y[t]+z[i,2]);if a[x[h],y[h]]=1 then//可以回到起点begink:=1;break;end;a[x[h],y[h]]:=3;end;inc(t);if k=1 then break;//找到解了until t>h;if k=1 then writeln('Yes') else writeln('No');//输出答案end;
end.

其实也没什么要讲的，bfs都差不多。

这篇关于P1363 幻想迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---