不讲效率,什么滚动数组,什么记录所有能通过的点都不用。只求明白意思。。
这程序样例都过不了,我还是看了N多题解才把架构大致弄好的。显然是以偏概全,没明白意思所以错的。
动态一上了二维以上我就不会怎么检查了。毫无头绪。
方向:1下 2左 3上 4右
a记录指令,mark记录道路,doit过程求不删时原来位置,k第几条指令,i,j坐标,t方向。
var n,m,i,j,x1,y1,k,t,k1,t1,i1,j1,sum:longint;
c:array[0..1000]of longint;
s:string;
s1:char;
f:array[0..1000,0..101,0..101,0..4]of integer;
a:array[0..1000]of longint;
mark:array[0..101,0..101]of boolean;
function min(x,y:longint):longint;
begin
min:=x; if y<min then min:=y;
end;
procedure readit;
var i,j,k,t:longint;
begin
readln(n,m,x1,y1); fillchar(mark,sizeof(mark),true);
for k:=1 to m do
for i:=1 to n do
for j:=1 to n do
for t:=1 to 4 do f[k,i,j,t]:=3000;
f[0,x1,y1,3]:=0;
for i:=1 to n do
begin
readln(s); for j:=1 to n do if s[j]='*' then mark[i,j]:=false;
end;
for i:=1 to m do
begin
readln(s);
if s[1]='F' then a[i]:=1;
if s[1]='B' then a[i]:=2;
if s[1]='L' then a[i]:=3;
if s[1]='R' then a[i]:=4;
end;
end;
procedure doit(kk,ii,jj,tt:longint);
begin
case a[kk] of
1: case tt of
1:begin i1:=ii-1; end;
2:begin j1:=jj+1; end;
3:begin i1:=ii+1; end;
4:begin j1:=jj-1; end;
end;
2: case tt of
1:begin i1:=ii+1; end;
2:begin j1:=jj-1; end;
3:begin i1:=ii-1; end;
4:begin j1:=jj+1; end;
end;
3: case tt of
1:begin t1:=tt+1; end;
2:begin t1:=tt+1 end;
3:begin t1:=tt+1; end;
4:begin t1:=1; end;
end;
4: case tt of
1:begin t1:=4; end;
2:begin t1:=tt-1 end;
3:begin t1:=tt-1 end;
4:begin t1:=tt-1 end;
end;
end;
end;
begin
readit;
for k:=1 to m do
for i:=1 to n do
for j:=1 to n do
for t:=1 to 4 do
if mark[i,j] then
if f[k,i,j,t]<3000 then
begin
i1:=i; j1:=j; t1:=t;
doit(k,i,j,t);
if f[k-1,i1,j1,t1]<3000 then
f[k,i,j,t]:=min(f[k-1,i,j,t]+1,f[k-1,i1,j1,t1]);
end;
sum:=9999;
for i:=1 to n do for j:=1 to n do for t:=1 to 4 do sum:=min(sum,f[m,i,j,t]);
writeln(sum);
end.
、、、、、、、、、、
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2011-4-19 12:23:00
有效耗时: 1547毫秒
测试结果1: 通过本测试点|有效耗时235ms
测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时156ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5: 通过本测试点|有效耗时156ms
测试结果6: 通过本测试点|有效耗时157ms
测试结果7: 通过本测试点|有效耗时156ms
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时156ms
测试结果10: 通过本测试点|有效耗时156ms
提交代码: view sourceprint?01.program rqnoj195;
02.var a,f:array[0..2001,0..2001] of boolean;
03.
i,j,k,l,m,n,t,step,min,x,y,x1,y1,x2,y2:longint;
04.procedure go(x,y:longint);
05.var h:boolean;
06.begin
07.h:=false;
08.inc(step);
09.if (x=x2)and(y=y2) then begin
10.if step<min then begin min:=step;dec(step);end
11.
else dec(step);
12.
end
13.
else begin
14.f[x,y]:=true;
15.if (x>1)and(a[x-1,y])and(not(f[x-1,y])) then begin go(x-1,y);h:=true;end;
16.if (x<n)and(a[x-1,y])and(not(f[x+1,y])) then begin go(x+1,y);h:=true;end;
17.if (y>1)and(a[x,y-1])and(not(f[x,y-1])) then begin go(x,y-1);h:=true;end;
18.if (y<m)and(a[x,y+1])and(not(f[x,y+1])) then begin go(x,y+1);h:=true;end;
19.if h then begin
20.dec(step);
21.f[x,y]:=false;
22.end
23.else dec(step);
24.end;
25.end;
26.
27.
begin
28.i:=0;
29.
read(n,m);
30.
for i:=1 to n do
31.
for j:=1 to m do
32.
begin
33.
read(t);
34.
if t=0 then a[i,j]:=true
35.
else a[i,j]:=false;
36.
end;
37.
read(x1,y1);
38.
read(x2,y2);
39.
min:=maxlongint;
40.
if (x1=x2)and(y1=y2) then begin
41.
writeln('0');
42.
halt;
43.
end
44.
else go(x1,y1);
45.
if min=maxlongint then writeln('No Answer!')
46.
else writeln(min-1);
47.
end.
其实挺简单的啦!