答案有200的
你想一下 搜到200 有多少种情况。。。。。。
我编了个DP的 没过// 郁闷中。
应该要考虑到记忆化搜索和dp是同一种过程的两种不同实现方式
对于状态稀疏的问题,记忆化搜索比dp会快不少
我昨天一时忘记了BFS 先找到的东西一定是最短的
然后晚上回去想了一下就觉得自己很白痴。。。
由于住校的问题,我要中午(现在)在可以过来发帖。。。没想到被你捷足先登,破坏我名誉。。。。。。。。
BFS版的AC程序如下
program li;
const d1:array[1..5] of longint=(-2,1,1,1,1);
d2:array[1..5] of longint=(-2,-1,0,1,2);
var x1,y1,x2,y2,tp1,tp2,i,x,y:longint;
a,b,c:array[0..100000] of longint;
f:array[0..210,0..210] of boolean;
begin
readln(x1,y1,x2,y2);
tp1:=1; tp2:=1;
a[1]:=x1; b[1]:=y1; c[1]:=0;
while tp1<=tp2 do
begin
x:=a[tp1]; y:=b[tp1];
for i:=1 to 5 do
if (x+d1[i]>=0) and (y+d2[i]>=0) and (x+d1[i]<=205) and (y+d2[i]<=205) and (not f[x+d1[i],y+d2[i]]) then
begin
inc(tp2);
a[tp2]:=x+d1[i];
b[tp2]:=y+d2[i];
c[tp2]:=c[tp1]+1;
f[a[tp2],b[tp2]]:=true;
if (a[tp2]=x2) and (b[tp2]=y2) then begin writeln(c[tp2]);halt end;
end;
inc(tp1);
end;
end.
供大牛鄙视//!
题目编号:351-libojie的化学作业 查看该题
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2009-6-13 12:47:00
有效耗时: 641毫秒
测试结果1: 通过本测试点|有效耗时141ms
测试结果2: 通过本测试点|有效耗时63ms
测试结果3: 通过本测试点|有效耗时63ms
测试结果4: 通过本测试点|有效耗时63ms
测试结果5: 通过本测试点|有效耗时47ms
测试结果6: 通过本测试点|有效耗时46ms
测试结果7: 通过本测试点|有效耗时62ms
测试结果8: 通过本测试点|有效耗时47ms
测试结果9: 通过本测试点|有效耗时47ms
测试结果10: 通过本测试点|有效耗时62ms
我是 小小小学生 的小号
用DP过了
至于 程序真的很白痴
因为 后面DP不到前面 前面又DP不到后面。。。
总是搞到有些地方算不到
于是有了以下代码。。。。。。。
绝对是无聊做出来的东西 大牛们见谅:
program li;
const d1:array[1..5] of longint=(-2,1,1,1,1);
d2:array[1..5] of longint=(-2,-1,0,1,2);
var x1,y1,x2,y2,i,j,k:longint;
a:array[0..300,0..300] of longint;
begin
readln(x1,y1,x2,y2);
for i:=0 to 205 do
for j:=0 to 205 do a[i,j]:=maxlongint;
a[x1,y1]:=0;
for i:=0 to 205 do
for j:=0 to 205 do
if a[i,j]<>maxlongint then
for k:=1 to 5 do
if (i+d1[k]>=0) and (j+d2[k]>=0) then
if a[i+d1[k],j+d2[k]]>a[i,j]+1 then
a[i+d1[k],j+d2[k]]:=a[i,j]+1;
for i:=205 downto 0 do
for j:=205 downto 0 do
if a[i,j]<>maxlongint then
for k:=1 to 5 do
if (i+d1[k]>=0) and (j+d2[k]>=0) then
if a[i+d1[k],j+d2[k]]>a[i,j]+1 then
a[i+d1[k],j+d2[k]]:=a[i,j]+1;
for i:=0 to 205 do
for j:=0 to 205 do
if a[i,j]<>maxlongint then
for k:=1 to 5 do
if (i+d1[k]>=0) and (j+d2[k]>=0) then
if a[i+d1[k],j+d2[k]]>a[i,j]+1 then
a[i+d1[k],j+d2[k]]:=a[i,j]+1;
for i:=205 downto 0 do
for j:=205 downto 0 do
if a[i,j]<>maxlongint then
for k:=1 to 5 do
if (i+d1[k]>=0) and (j+d2[k]>=0) then
if a[i+d1[k],j+d2[k]]>a[i,j]+1 then
a[i+d1[k],j+d2[k]]:=a[i,j]+1;
writeln(a[x2,y2]);
end.
状态题目:libojie的化学作业
题目编号:351-libojie的化学作业 查看该题
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2009-6-13 13:00:00
有效耗时: 782毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时62ms
测试结果3: 通过本测试点|有效耗时62ms
测试结果4: 通过本测试点|有效耗时47ms
测试结果5: 通过本测试点|有效耗时63ms
测试结果6: 通过本测试点|有效耗时47ms
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 通过本测试点|有效耗时63ms
测试结果9: 通过本测试点|有效耗时47ms
测试结果10: 通过本测试点|有效耗时172ms