# 48 条题解

• @ 2019-07-22 19:55:12

vector记录路径，dfs搜索。
字典序搜索顺序，左上下右。

``````#include <iostream>
#include <vector>

using namespace std;

typedef struct
{
int x,y;
}point;

int n,m;
char ma[6][6]={0};
vector<point> path;
int ans=0;

void dfs(vector<point> &pa,int x,int y,int now)
{
point push;
push.x=x;
push.y=y;
pa.push_back(push);
now++;
ma[x][y]='*';
if(now>ans)
{
ans=now;
path=pa;
}
if(x>1)
{
if(ma[x-1][y]=='1')
{
dfs(pa,x-1,y,now);
}
}
if(y>1)
{
if(ma[x][y-1]=='1')
{
dfs(pa,x,y-1,now);
}
}
if(y<m)
{
if(ma[x][y+1]=='1')
{
dfs(pa,x,y+1,now);
}
}
if(x<m)
{
if(ma[x+1][y]=='1')
{
dfs(pa,x+1,y,now);
}
}
ma[x][y]='1';
pa.pop_back();
}

int main()
{
cin>>n>>m;
int i,j;
int x,y;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>ma[i][j];
if(ma[i][j]=='S')
{
x=i;y=j;
}
}
}
vector<point> pa;
dfs(pa,x,y,0);
cout<<ans<<endl;
cout<<endl;
for(i=0;i<path.size();i++)
{
cout<<'('<<path[i].x<<','<<path[i].y<<')'<<endl;
}
return 0;
}
``````
• @ 2015-05-17 14:31:54

const dx:array[1..4] of longint=(-1,0,0,1);
dy:array[1..4] of longint=(0,-1,1,0);
var n,m,i,j,x,y,ans:longint;
a:array[0..100,0..100] of char;
b,f:array[1..10000] of longint;
procedure dfs(x,y,s:longint);
var i,nx,ny:longint;
begin
for i:=1 to 4 do begin
nx:=x+dx[i];
ny:=y+dy[i];
if a[nx,ny]='1' then begin
a[nx,ny]:='*';
b[s]:=i;
dfs(nx,ny,s+1);
a[nx,ny]:='1';
end;
end;
if s>ans then begin
ans:=s;
for i:=1 to s-1 do f[i]:=b[i];
end;
end;
begin
for i:=1 to n do begin
a[i,0]:='0';
a[i,m+1]:='0';
end;
for i:=1 to m do begin
a[0,i]:='0';
a[n+1,i]:='0';
end;
for i:=1 to n do begin
for j:=1 to m do begin
if a[i,j]='S' then begin
x:=i;
y:=j;
end;
end;
end;
ans:=1;
a[x,y]:='*';
dfs(x,y,1);
writeln(ans);
writeln;
for i:=1 to ans-1 do begin
writeln('(',x,',',y,')');
x:=x+dx[f[i]];
y:=y+dy[f[i]];
end;
writeln('(',x,',',y,')');
end.

• @ 2012-08-04 19:46:47

坑爹 没注意字典序 所以四个方向搜索时随便打的。。。

• @ 2012-07-21 19:33:24

一次AC了！

program Project1;

const dx:array[1..4] of longint=(-1,0,0,1);

dy:array[1..4] of longint=(0,1,-1,0);

var a:array[0..5,0..5] of boolean;

ans,sx,sy,m,n,up:longint;

zzz:array[0..20000] of record

x,y:longint;

end;

pre:array[0..5,0..5] of record

xx,yy:longint;

end;

procedure init;

var i,j:longint;

ch:char;

begin

assign(input,'1.in');reset(input);

assign(output,'1.out');rewrite(output);

for i:=1 to n do

begin

for j:=1 to m do

begin

if ch='S' then

begin

sx:=i;

sy:=j;

a[sx,sy]:=true;

end else

if ch='1' then a:=true else a:=false;

end;

end;

up:=0;

end;

procedure push(x,y:longint);

begin

inc(up);

zzz[up].x:=x;

zzz[up].y:=y;

end;

procedure jilu(x,y:longint);

begin

if (x=sx)and(y=sy) then

begin

push(x,y);

exit;

end;

jilu(pre[x,y].xx,pre[x,y].yy);

push(x,y);

end;

function wulu(x,y:longint):boolean;

var i,kx,ky:longint;

begin

for i:=1 to 4 do

begin

kx:=x+dx[i];

ky:=y+dy[i];

if (kx>=1)and(kx=1)and(kyans then

begin

ans:=depth;

up:=0;

jilu(x,y);

end;

exit;

end;

for i:=1 to 4 do

begin

kx:=x+dx[i];

ky:=y+dy[i];

if (kx>=1)and(kx=1)and(ky

• @ 2010-04-05 17:01:13

终于过了！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

• @ 2009-11-19 20:03:05

一次AC, RP++

#include

using namespace std;

int m, n;

int maxest = 0;

int a[6][6] = {0};

int b[6][6] = {0};

int c[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

struct way

{

int x;

int y;

}w[30], r[30];

void dfs(int x, int y, int sum)

{

int i;

int nx, ny;

w[sum].x = x;

w[sum].y = y;

if (sum > maxest)

{

memcpy(r, w, 30*8);

maxest = sum;

}

b[x][y] = true;

for (i = 0; i 0 && nx 0 && ny >m>>n;

for (i = 1; i ch;

switch (ch)

{

case '0':

a[i][j] = false;

break;

case '1':

a[i][j] = true;

break;

case 'S':

a[i][j] = true;

sx = i;

sy = j;

break;

}

}

}

dfs(sx, sy, 1);

cout

• @ 2009-11-09 08:19:54

囧...程序完全写错竟然还能70分...

• @ 2009-11-03 00:10:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

想复杂了....

还去排序....又3次AC

一开始觉得是BFS...后来发现只能用DFS..

注意搜索顺序即可.

• @ 2009-11-02 08:15:12

呵呵，第120个人通过。。。。。

DFS就相当简单了，主要是记录路径。。。。。我这个巨菜想了我半个小时。。。。。

下面是我的程序咯。。。。应该排版的挺好看的了。。。。

program VIJOSP1681;

const

d:array [1..4,1..2] of integer=((-1,0),(0,-1),(0,1),(1,0));

type

wtype=record

wx,wy:longint;

end;

var

ans,w:array [0..25] of wtype;

a,b:array [0..6,0..6] of boolean;

i,j,n,m,sum,max,sx,sy:longint;

ch:char;

procedure search(x,y,sum:longint);

var

tx,ty,i:longint;

begin

b[x,y]:=false;

w[sum].wx:=x;

w[sum].wy:=y;

if sum>max then begin

max:=sum;

ans:=w;

end;

for i:=1 to 4 do begin

tx:=x+d;

ty:=y+d;

if a[tx,ty] and b[tx,ty] then

search(tx,ty,sum+1);

end;

b[x,y]:=true;

end;

begin

for i:=1 to n do begin

for j:=1 to m do begin

case ch of

'0':a:=false;

'1':a:=true;

'S':begin

sx:=i;

sy:=j;

end;

end;

end;

end;

fillchar(b,sizeof(b),true);

search(sx,sy,1);

writeln(max);

writeln;

for i:=1 to max do writeln('(',ans[i].wx,',',ans[i].wy,')');

end.

• @ 2009-11-01 00:02:22

program p1681;

const

di:array[1..4] of longint=(-1,0,0,1);

dj:array[1..4] of longint=(0,-1,1,0);

var

i,j,l,m,n,ans:Longint;

s1,s2:longint;

ch:string;

a:array[0..5,0..5] of String;

can:array[0..5,0..5] of Boolean;

t1,t2,ans1,ans2,tmp:string;

procedure dfs(x,y,depth:longint);

var

i:longint;

tmp1,tmp2:string;

begin

if depth>ans then begin

ans:=depth;

ans1:=t1;

ans2:=t2;

end;

for i:=1 to 4 do

if (x+di[i]>0) and (x+di[i]0) and (y+dj[i]

• @ 2009-10-31 21:15:43

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

简单DFS.水.主要是确定方向.先上再左再右再下

• @ 2009-10-30 20:46:03

刚好第100个AC说。。。

• @ 2009-10-30 18:13:41

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

why?

• @ 2009-10-29 22:28:30

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-10-29 21:19:40

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行超时|格式错误...

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行超时|格式错误...

├ 测试数据 10：运行超时|格式错误...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：70 有效耗时：0ms

var

xx,yy,l,max,x,y,i,j,m,n:longint;

b:array[0..6,0..6]of boolean;

q:array[1..1000000,1..3]of longint;

f:array[0..6,0..6]of longint;

c:char;

procedure dfs(x,y,s:longint);

begin

inc(l);

q[l,1]:=x;

q[l,2]:=y;

q[l,3]:=s;

b[x,y]:=false;

if b[x-1,y]

then dfs(x-1,y,s+1);

if b[x,y-1]

then dfs(x,y-1,s+1);

if b[x,y+1]

then dfs(x,y+1,s+1);

if b[x+1,y]

then dfs(x+1,y,s+1);

b[x,y]:=true;

if max

• @ 2009-10-29 11:49:54

真郁闷

…………

…………

6K 上说编译未通过

Sunny 则一直在Running

之后再交一遍 就AC了~~

一模一样的程序呀~

另外 lx的顺序MS是错的

应该是

dfs(x-1,y);

dfs(x,y-1);

dfs(x,y+1);

dfs(x+1,y);

起码我的是这样，但也可能是程序不同的缘故

• @ 2009-10-28 21:47:42

dfs(x-1,y);

dfs(x,y+1);

dfs(x,y-1);

dfs(x+1,y);

• @ 2009-10-28 19:12:25

很水……不过想问一下，有没有办法直接通过决策的优先顺序来直接生成字典序最小的路径？我是写了compare的……

• @ 2009-10-28 18:32:34

确实挺水，故用BFS来难为以下自己。

• @ 2009-10-28 17:56:46

如此水题，做了我50MIN！！！ 注意：S是大写的！！！

ID
1681

6

805

227

28%

3