48 条题解
-
1
Lifi LV 10 @ 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; } -
0
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
readln(n,m);
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
read(a[i,j]);
if a[i,j]='S' then begin
x:=i;
y:=j;
end;
end;
readln;
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. -
0
一次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);
readln(m,n);
for i:=1 to n do
begin
for j:=1 to m do
begin
read(ch);
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;
readln;
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 -
0
LV 0 @ 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 -
0
编译通过...
├ 测试数据 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..
注意搜索顺序即可. -
0
呵呵，第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
readln(n,m);
for i:=1 to n do begin
for j:=1 to m do begin
read(ch);
case ch of
'0':a:=false;
'1':a:=true;
'S':begin
sx:=i;
sy:=j;
end;
end;
end;
readln;
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. -
0
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] -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
简单DFS.水.主要是确定方向.先上再左再右再下 -
0
wangshan0908 LV 10 @ 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? -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
wwwhhhyyywhy LV 8 @ 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 有效耗时：0msvar
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 -
0
guori12321 LV 8 @ 2009-10-28 17:56:46
如此水题，做了我50MIN！！！ 注意：S是大写的！！！
Lifi
LV 10
@ 2019-07-22 19:55:12
