讨论 / 深搜也行啊
B-L-A-C-K 2010-08-05 05:19:00
点我顶贴 收藏 删除
没意思的深搜也能AC啊

program p195;

var a:array[1..2000,1..2000]of integer;

f:array[1..2000,1..2000]of boolean;

i,j,m,n,min,dep,x0,y0,x1,y1:longint;

procedure work(x,y:longint);

begin

inc(dep);

if (x=x1)and(y=y1) then

begin

if dep<min then min:=dep;

dec(dep)

end

else if dep>min then dec(dep)

else begin

f[x,y]:=true;

if (x>1)and(a[x-1,y]=0)and(not f[x-1,y]) then work(x-1,y);

if (y>1)and(a[x,y-1]=0)and(not f[x,y-1]) then work(x,y-1);

if (x<n)and(a[x+1,y]=0)and(not f[x+1,y]) then work(x+1,y);

if (y<m)and(a[x,y+1]=0)and(not f[x,y+1]) then work(x,y+1);

f[x,y]:=false;

dec(dep)

end

end;

begin

read(n,m);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

read(x0,y0,x1,y1);

min:=maxlongint;

work(x0,y0);

if min<maxlongint then write(min-1) else write(’No Answer!’)

end.

#1 玉十三殒@2008-10-29 01:54:00
回复 删除
没意思也做出来了~

: D

#2 Wych@2008-10-29 08:26:00
回复 删除
回问楼主:

用你的标准程序输入电脑

2.0.4版本的free pascal IDE为什么会出现

while link error 这个编译错误,而在RQNOJ上却能AC而无出现No Compiler状态呢?

那么还有while link error到底是什么错误呢?

#3 飞雪天涯@2008-10-29 08:29:00
回复 删除
我记忆化搜索的。

#include<iostream>

#include<climits>

#define NoPath -1

#define Bricked -1

using namespace std;

int dyna[22][22];

int m,n,xf,xt,yf,yt;//x,y from,to

bool maze[22][22],visited[22][22];

int dfs(int x,int y){

//cout<<"dfs("<<x<<","<<y<<");"<<endl;

if (x==xt&&y==yt) dyna[x][y]=0;

if (!maze[x][y]) dyna[x][y]=Bricked;

if (dyna[x][y]!=-2){

//cout<<"1)dyna["<<x<<"]["<<y<<"]="<<dyna[x][y]<<endl;

return dyna[x][y];

}

visited[x][y]=true;

bool visible=false;

int minlen=INT_MAX;

int dir[5][3]={{0,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0}};

for (int d=1;d<=4;d++){

if (!visited[x+dir[d][1]][y+dir[d][2]]&&maze[x+dir[d][1]][y+dir[d][2]]){

int k=dfs(x+dir[d][1],y+dir[d][2])+1;

if (k-1!=NoPath&&k-1!=Bricked){

//cout<<"visited"<<x+dir[d][1]<<y+dir[d][2]<<endl;

if (k<minlen) minlen=k;

visible=true;

}

}

}

if (!visible) dyna[x][y]=NoPath;

else dyna[x][y]=minlen;

//cout<<"2)dyna["<<x<<"]["<<y<<"]="<<dyna[x][y]<<endl;

visited[x][y]=false;

return dyna[x][y];

}

int main(void){

cin>>n>>m;

memset(maze,false,sizeof(maze));

memset(visited,false,sizeof(visited));

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++){

int k;cin>>k;

if (k==0) maze[i][j]=true;

dyna[i][j]=-2;

}

cin>>xf>>yf;

cin>>xt>>yt;

//for (int i=1;i<=n;i++)

// for (int j=1;j<=m;j++){

// cout<<"maze["<<i<<"]["<<j<<"]="<<maze[i][j]<<endl;

// cout<<"dyna["<<i<<"]["<<j<<"]="<<dyna[i][j]<<endl;

// }

//memset(dyna,-2,sizeof(dp));

int ans=dfs(xf,yf);

if (ans==NoPath||ans==Bricked) cout<<"No Answer!";

else cout<<ans;

//while(1);

return 0;

}

/*

5 5

1 1 1 1 1

1 1 1 0 0

1 0 0 0 1

0 0 1 0 0

1 1 1 0 1

4 1

5 4

===========

6

*/

#4 宇智波带猪@2008-10-30 01:18:00
回复 删除
while link error

俗称“林肯错误”

是fp不稳定时的表现

#5 B-L-A-C-K@2008-10-30 05:02:00
回复 删除
while link error

我也遇到过,重新保存一下就OK了

#6 zhaoyimei@2009-10-08 02:55:00
回复 删除
很容易看懂的深搜,经典
#7 leapoahead@2010-08-05 05:19:00
回复 删除
。这本来就可以深搜
查看更多回复
提交回复