P3610 奶牛导航

大家好，欢迎来到IT知识分享网。

这题算是P1126 机器人搬重物的升级版QAQ，就是把他当成两只牛来算就好了

const z:array[1..4,1..2]of -1..1=((-1,0),(0,1),(1,0),(0,-1)); var i,j,k:longint; n:longint; bo:array[0..21,0..21,0..21,0..21,1..4,1..4]of boolean; //6维数组，为第一只牛的坐标、方向，第二只牛的坐标、方向 no:array[0..21,0..21]of boolean; x1,y1,x2,y2,u,fx1,fx2:array[0..]of longint; _x1,_y1,_x2,_y2,_fx1,_fx2:longint; ch:char; h,t:longint; x1i,y1i,x2i,y2i:longint; procedure add(x1,y1,x2,y2:longint);//当前这一格是可以走的 var i,j:longint; begin for i:=1 to 4 do for j:=1 to 4 do bo[x1,y1,x2,y2,i,j]:=true; end; function left(fx:longint):longint;//左转 begin if fx=1 then exit(4) else exit(fx-1); end; function right(fx:longint):longint;//右转 begin if fx=4 then exit(1) else exit(fx+1); end; procedure go(fx:longint;var x,y:longint);//判断可不可以走... begin if (x=1) and (y=n) then exit;//到了终点就不可以走了 if no[x+z[fx,1],y+z[fx,2]] then//移动 begin x:=x+z[fx,1]; y:=y+z[fx,2]; end; end; begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(ch); if ch='E' then no[i,j]:=true; end; readln; end; //判断用的数组初始化 for x1i:=1 to n do for y1i:=1 to n do for x2i:=1 to n do for y2i:=1 to n do if no[x1i,y1i] and no[x2i,y2i] then add(x1i,y1i,x2i,y2i); //队列初始化 h:=1; t:=1; x1[1]:=n; y1[1]:=1; x2[1]:=n; y2[1]:=1; u[1]:=0; fx1[1]:=1; fx2[1]:=2; bo[x1[1],y1[1],x2[1],y2[1],fx1[1],fx2[1]]:=false; repeat if (x1[t]=1) and (x2[t]=1) and (y1[t]=n) and (y2[t]=n) then//两只牛都到终点了 begin write(u[t]); exit; end; for i:=1 to 3 do begin if i=1 then begin //记录下来比较方便 _x1:=x1[t]; _y1:=y1[t]; _x2:=x2[t]; _y2:=y2[t]; go(fx1[t],_x1,_y1); go(fx2[t],_x2,_y2); if(bo[_x1,_y1,_x2,_y2,fx1[t],fx2[t]])then//判断向前走可不可以 begin//入队列 inc(h); x1[h]:=_x1; y1[h]:=_y1; x2[h]:=_x2; y2[h]:=_y2; fx1[h]:=fx1[t]; fx2[h]:=fx2[t]; bo[_x1,_y1,_x2,_y2,fx1[t],fx2[t]]:=false; u[h]:=u[t]+1; end; end; if i=2 then if(bo[x1[t],y1[t],x2[t],y2[t],left(fx1[t]),left(fx2[t])])then//左转 //转弯不会到地图外面和草上，不用特判 begin inc(h); fx1[h]:=left(fx1[t]); fx2[h]:=left(fx2[t]); x1[h]:=x1[t]; y1[h]:=y1[t]; x2[h]:=x2[t]; y2[h]:=y2[t]; bo[x1[h],y1[h],x2[h],y2[h],fx1[h],fx2[h]]:=false; u[h]:=u[t]+1; end; if i=2 then if(bo[x1[t],y1[t],x2[t],y2[t],right(fx1[t]),right(fx2[t])])then//右转QAQ begin inc(h); fx1[h]:=right(fx1[t]); fx2[h]:=right(fx2[t]); x1[h]:=x1[t]; y1[h]:=y1[t]; x2[h]:=x2[t]; y2[h]:=y2[t]; bo[x1[h],y1[h],x2[h],y2[h],fx1[h],fx2[h]]:=false; u[h]:=u[t]+1; end; end; inc(t); until t>h; end. 

就是写起来累点，思路还是很清楚的QAQWQ