CF540C Ice Cave

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

这题就是一个裸的BFS，luogu的翻译不好，建议看原文QAQ

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;ch:char;a,b:array[0..601,0..601]of boolean;x,y:array[0..1000000]of longint;fx,fy,lx,ly:longint;
procedure yes;//写成过程方便
beginwrite('YES');halt;
end;
procedure no;
beginwrite('NO');halt;
end;
beginreadln(m,n);for i:=1 to m dobeginfor j:=1 to n dobeginread(ch);if ch='X' then a[i,j]:=false;//不要看翻译那么玄学，就是不能走就好了if ch='.' then a[i,j]:=true;end;readln;end;readln(fx,fy,lx,ly);a[fx,fy]:=true;if (fx=lx)and(fy=ly) then//起点和终点相同的特判begink:=0;for i:=1 to 4 doif a[lx+z[i,1],ly+z[i,2]] then inc(k);if k<1 then no else yes;end;if a[lx,ly] then//如果终点是浮冰，则要到终点旁的一个点绕一下begink:=0;for i:=1 to 4 doif a[lx+z[i,1],ly+z[i,2]] then inc(k);if k<2 then no;//所以必须要有2个及以上的浮冰end elsea[lx,ly]:=true;//终点赋成true，BFS起来方便//队列的初始化，不多说h:=1;t:=1;x[1]:=fx;y[1]:=fy;repeatif(x[t]=lx)and(y[t]=ly)then yes;//到终点了QAQfor i:=1 to 4 doif a[x[t]+z[i,1],y[t]+z[i,2]] thenbegin//进入队列inc(h);a[x[t]+z[i,1],y[t]+z[i,2]]:=false;x[h]:=x[t]+z[i,1];y[h]:=y[t]+z[i,2];end;inc(t);//出队until t>h;no;//走不到QAQ
end.

裸的BFS但是代码不短啊QAQ

这篇关于CF540C Ice Cave的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---