本文主要是介绍P1519 穿越栅栏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
usaco里的搜索其实还是不错的,这自然也不是一道水题(其实是我题目看错了)
这类题目一般都是一题多解,既然如此垃圾的我自然用bfs
const z:array[1..4,1..2]of -1..1=((1,0),(0,1),(-1,0),(0,-1));
var i,j,k:longint;a,b:array[0..1000,0..1000]of boolean;p:array[0..1000,0..1000]of longint;x,y,u:array[0..1010101]of longint;m,n,x1,y1,x2,y2,h,t,max:longint;ch:char;
procedure bfs(x1,y1:longint);//一个裸的bfs
var h,t,i,j,k:longint;
beginh:=1;t:=1;x[1]:=x1;y[1]:=y1;b:=a;u[1]:=0;while h>=t dobeginfor i:=1 to 4 doif b[x[t]+z[i,1],y[t]+z[i,2]] thenbegininc(h);b[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];u[h]:=u[t]+1;if u[h]<p[x[h],y[h]] then p[x[h],y[h]]:=u[h];//记录最优解,因为有两个出口end;inc(t);end;
end;
beginread(n,m);readln;//读入麻烦一点for i:=1 to m*2+1 dobeginfor j:=1 to n*2+1 dobeginread(ch);if ch=' ' thenbegina[i,j]:=true;endelsebegina[i,j]:=false;end;if (i=1) or (i=m*2+1) or (j=1) or (j=n*2+1) then//在边上if ch=' ' thenbeginif (x1=0) and (y1=0) thenbeginx1:=i;y1:=j;endelsebeginx2:=i;y2:=j;end;end;end;readln;end;p[x1,y1]:=1;p[x2,y2]:=1;for i:=1 to m*2+1 dofor j:=1 to n*2+1 dobeginp[i,j]:=maxlongint;//初值end;//两个出口bfs(x1,y1);bfs(x2,y2);for i:=2 to m*2 dofor j:=2 to n*2 do if (p[i,j]>max) and (p[i,j]<>maxlongint) and (i mod 2=0) and (j mod 2=0) then {找最大值}max:=p[i,j];write(max div 2+1);//因为记录的是格数不是字符数
end.
最后才发现这题难度其实是在读入和处理。还是蛮水的
这篇关于P1519 穿越栅栏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!