[USACO2007 OCT] Silver Obstacle Course 障碍训练场[Test23T1 ]
Time Limit:1000MS Memory Limit:65536K
Total Submit:103 Accepted:62
Description
障碍训练场
考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。
例如下图：
. . B x .
. x x A .
. . . x .
. x . . .
. . x . .
贝茜发现自己恰好在点A出，她想去B处的盐块添盐。缓慢而且笨拙的动物，比如奶牛，十分讨厌转弯。尽管如此
当然在必要的时候她们还是会转弯的。对于一个给定的牧场，请你计算从A到B最少的转弯次数。开始的时候
贝茜可以使面对任意一个方向。贝茜知道她一定可以到达。
Input
* 行 1: 一个整数 N
* 行 2..N + 1: 行 i+1 有 N 个字符 ('.', 'x', 'A', 'B')，表示每个点的状态。
Output
* 行 1: 一个整数，最少的转弯次数。
Sample Input
3 .xA ... Bx.
Sample Output
2
用广搜
const
dx:array[1..4]of -1..1=(0,1,0,-1);
dy:array[1..4]of -1..1=(1,0,-1,0);
var
t,w,x,y,z,i,j,ii,jj,mm,nn,n,a,b:longint;
s:ansistring;
xx:array[1..1000,1..1000]of char;
h:array[0..1000000,1..4]of longint;
procedure doing;
begin
t:=0; w:=0; h[0,2]:=ii; h[0,3]:=jj;
repeat
for i:=1 to 4 do
begin
x:=1;
y:=dx[i]*x+h[t,2]; z:=dy[i]*x+h[t,3];
while (y>0)and(y<=n)and(z>0)and(z<=n)and(xx[y,z]<>'x')and(i<>h[t,1]) do
begin
inc(w); xx[y,z]:='y';
h[w,1]:=i; h[w,2]:=y; h[w,3]:=z;
if t<>0 then h[w,4]:=h[t,4]+1;
if (h[w,2]=mm)and(h[w,3]=nn) then
begin
writeln(h[w,4]);
readln;
halt;
end;
inc(x);
y:=dx[i]*x+h[t,2]; z:=dy[i]*x+h[t,3];
end;
end;
if h[t+1,4]>h[t,4] then for i:=1 to w do if xx[h[i,2],h[i,3]]='y' then xx[h[i,2],h[i,3]]:='x';
inc(t);
until t>w;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(s);
for j:=1 to n do
begin
xx[i,j]:=s[j];
if xx[i,j]='A' then
begin
ii:=i;
jj:=j;
end;
if xx[i,j]='B' then
begin
mm:=i;
nn:=j;
end;
end;
end;
doing;
end.
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息