讨论 / 哪个大牛发个程序看看?
webeskycn 2009-06-12 22:03:00
点我顶贴 收藏 删除
我用BFS写的。但是实在不知道哪儿错了。

哪个大牛能发个代码出来看看??

#1 小小小学生@2009-06-12 02:26:00
回复 删除
BFS搜索出来太多了

答案有200的

你想一下 搜到200 有多少种情况。。。。。。

我编了个DP的 没过// 郁闷中。

#2 wish@2009-06-12 02:40:00
回复 删除
我写了记忆化搜索通过了

应该要考虑到记忆化搜索和dp是同一种过程的两种不同实现方式

对于状态稀疏的问题,记忆化搜索比dp会快不少

#3 小小小学生@2009-06-12 21:49:00
回复 删除
WISH。。。。

我昨天一时忘记了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.

供大牛鄙视//!

#4 小小小学生@2009-06-12 22:03:00
回复 删除
状态题目:libojie的化学作业

题目编号: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

#5 小号一个@2009-06-12 22:03:00
回复 删除
首先介绍一下//

我是 小小小学生 的小号

用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

查看更多回复
提交回复