64 条题解
-
0
sduer LV 6 @ 2009-02-13 14:22:00
晕，没人用c++吗.......
#include
using namespace std;
const int MAX = 3000;
int graph[MAX][MAX];
int n,m;
int maxx,maxy;
int ans;void DFS(int d,int x,int y){
graph[x][y] = 1;
if( d > ans ){
ans = d;
maxx = x;
maxy = y;
}if( x+1 < n && graph[x+1][y] == 0)
DFS(d+1,x+1,y);if( x-1 >= 0 && graph[x-1][y] == 0)
DFS(d+1,x-1,y);if( y+1 < m && graph[x][y+1] == 0)
DFS(d+1,x,y+1);if( y-1 >= 0 && graph[x][y-1] == 0)
DFS(d+1,x,y-1);graph[x][y] = 0;
}//end for DFS
int main(){
cin >> n >> m;
char key;
ans = 0;
int tempx,tempy;for(int i=0;i key;
if(key == '#'){
graph[i][j] = 1;
}else{
tempx = j;
tempy = i;
graph[i][j] = 0;
}}
}//end for input;DFS(0,tempx,tempy);
DFS(0,maxx,maxy);cout
-
0
nezerlands LV 8 @ 2009-01-30 21:42:56
var
a:array[0..1010,0..1010] of char;
i,j,m,n,open,clsed:longint;
v:array[1..10000,1..2] of integer;
ans,max:integer;
procedure search(i,j:integer);
begin
if a='.' then
inc(max);
a:='#';
while openans then ans:=max;
end;
end;
writeln(ans-1);
end. -
0
huangzeyuand LV 3 @ 2008-11-10 08:31:42
water
-
0
只是核心代码，仅供参考：
procedure search (x,y,total:integer);
var
k:integer;
flag:boolean;
begin
v[x,y]:=true;
flag:=false;
for k:=1 to 4 do
if (x+vx[k]0) and (y+vy[k]0) then
if (not v[x+vx[k],y+vy[k]]) and (map[x+vx[k],y+vy[k]]='.')then
begin
flag:=true;
search (x+vx[k],y+vy[k],total+1);
end;if (not flag) and (total>last) then
begin
yx:=x;
yy:=y;
last:=total;
if last>ans then ans:=last;
end;end;
procedure nsearch (x,y,total:integer);
var
k:integer;
flag:boolean;
begin
g[x,y]:=true;
flag:=false;
for k:=1 to 4 do
if (x+vx[k]0) and (y+vy[k]0) then
if (not g[x+vx[k],y+vy[k]]) and (map[x+vx[k],y+vy[k]]='.')then
begin
flag:=true;
nsearch (x+vx[k],y+vy[k],total+1);
end;if (not flag) and (total>ans)then ans:=total;
end;
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
fammiebright LV 9 @ 2008-11-01 17:32:38
我怎么觉得证明过程有点像树网的核？
-
0
题目中的原话：
假设任意的两个风景点都有且仅有一条路径（无回路）相连。显然，任意一个风景点都可以作为游览路线的起点或者终点。证明：
由上面的描述可以说明该图为一棵树，只要从树的任意一个叶子节点为起点，DFS找出最长的一条路径，这条路径的终点必然也是叶子。
1）如果你选做起点的叶子是深度最深的叶子A(RP真好，这都选到了....)，那么以它为起点DFS，找出的终点B必然是第二深的节点，再以B为起点DFS，又会回到A点，叶子A和B的深度和必然是所有叶子对的深度和中最大的，也就是题目中要求的最长路径。
2）如果你选的不是最深的，那第一遍DFS搜出的终点就是最深的叶子A，以A为起点DFS找到的为第二深的叶子，证明同上。不知道对不对，如果有错，请各位大牛指出~
其实想明白了就很容易了 -
0
程序仅供参考．程序简单，不要简单去copy
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
procedure dfs(d,x,y:longint);
var i,j,k,t:longint;
begin
map[x,y]:=1;
if d>ans then begin ans:=d;maxx:=x;maxy:=y; end;
if map[x+1,y]=0 then dfs(d+1,x+1,y);
if map[x-1,y]=0 then dfs(d+1,x-1,y);
if map[x,y+1]=0 then dfs(d+1,x,y+1);
if map[x,y-1]=0 then dfs(d+1,x,y-1);
map[x,y]:=1;
end;
dfs(0,maxx,maxy);
dfs(0,maxx,maxy);
秒杀．
简单题．．但证明很好用．． -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 384ms
├ 测试数据 05：运行超时...
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：384ms
编译通过...
├ 测试数据 01：答案正确... 259ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：运行超时...
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：80 有效耗时：259ms
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 509ms
├ 测试数据 05：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：509ms源程序完全没改过……让我交3次……我sun……
-
0
iNeverKnow LV 3 @ 2008-10-15 20:30:39
证明两次DFS的正确性:
任意搜索出一个点A，则A应为边界点。设一次DFS后找出的最长边的终点为B。若AB不是最长边，则最长边必不经过A。于是问题等价证明：不存在最长边同时不经过A、B两点。假设存在最长边为CD，因为题中说任意两点间都有路径，设AB上的P和CD上的Q连通，由第一次DFS的结果知PB>PQ+QD，所以PB+PQ>QD，故CB=CQ+QP+PB>CQ+QD=CD。于CD最长矛盾。证毕。 -
0
编译通过...
├ 测试数据 01：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 02：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：运行时错误...| 错误号: 202 | 堆栈溢出错
├ 测试数据 05：运行时错误...| 错误号: 202 | 堆栈溢出错
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：20 有效耗时：0ms
我再对比上一个....P.S 原来是true打成false...
sduer
LV 6
@ 2009-02-13 14:22:00
