208  Firetruck
Moderator: Board moderators
To Problem setter: Problem 208 Firetruck
I feel exhausted about this problem. I am quite sure I have implemented a correct algorithm to this problem, which handled all cases, at least for those I thought of.
Could the problem setter give me a clear image on the problem description? Since the problem description is not clear enough, for example how to handle some special cases.
1. What if the nearest corner is #1, i.e. the firestation? Should I output 1 route or 0 route?
2. What's the output format in detail? Are the numbers of width 4? Should I obmit the 's' when there's only 1 route?
Could the problem setter give me a clear image on the problem description? Since the problem description is not clear enough, for example how to handle some special cases.
1. What if the nearest corner is #1, i.e. the firestation? Should I output 1 route or 0 route?
2. What's the output format in detail? Are the numbers of width 4? Should I obmit the 's' when there's only 1 route?

 Learning poster
 Posts: 63
 Joined: Thu Apr 04, 2002 2:00 am
http://www.acm.inf.ethz.ch/ProblemSetAr ... 1/acm91a.c
This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE.
This is the "official" backtracking solution, which should make the output format clearer, but don't try it on Valladolid, it gets TLE.

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
208  Firetruck
Does anyone know faster method than simple DFS to solve this problem ?
I use DFS in my solution, but got TLE .... Could anyone help me ?
I use DFS in my solution, but got TLE .... Could anyone help me ?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
Wow!
Adrian's idea is absolutely COOL! Never thought about that and was wondering why would I get a TLE.. so, the judging data should include one like:
2
1 2
1 3
1 4
..
1 20
.. and nodes from 3 to 20 form a completed graph. Huh
Learned a lot from this problem. Thanks!
2
1 2
1 3
1 4
..
1 20
.. and nodes from 3 to 20 form a completed graph. Huh
Learned a lot from this problem. Thanks!
JongMan @ Yonsei
1... if you use link list... you should sort it firstxenon wrote:No problem
I had a long standing TLE on this problem too. Adrian's hints made me look at the code again, and make some adjustments.
Now I have WA in 0.000 seconds! So obviously the code is bad in some cases, although it still solves the examples.
Any tips?
2... if input like
1
2 3
2 4
3 3
0 0
output is
1
There are 1 routes from the firestation to streetcorner 1.
I have done what u had said and i still cant past the judge....
can anyone give me more special cases?? Thanks
The following is my code(i will appreciate very much if u can point out my mistakes):
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAX 22
int i,j,k,t,m,cnt,tar,num,count,a,b,tmp,map[MAX][MAX],n[MAX],p[MAX][MAX],ans[MAX];
int next[MAX][MAX],nu[MAX];
bool used[MAX],l,d[MAX];
void dfs2(int x)
{
int e,f;
used[x]=1;
ans[tmp++]=x;
if(x==tar)
{
for(e=0;e<tmp;e++)
{
if(e>0)
printf(" ");
printf("%d",ans[e]);
}
printf("\n");
tmp;
used[x]=0;
count++;
return ;
}
for(e=0;e<nu[x];e++)
{
if(!used[next[x][e]])
dfs2(next[x][e]);
}
tmp;
used[x]=0;
}
void dfs(int x)
{
int e,f,g;
used[x]=1;
if(x==1)
{
used[x]=0;
return;
}
for(e=0;e<n[x];e++)
{
if(!used[p[x][e]])
{
for(f=0,g=0;f<nu[p[x][e]];f++)
{
if(next[p[x][e]][f]==x)
{
g=1;
break;
}
}
if(g==0)
{
next[p[x][e]][nu[p[x][e]]++]=x;
dfs(p[x][e]);
}
}
}
used[x]=0;
}
int presort(const void *m1, const void *m2)
{
return *((int*)m1)*((int*)m2);
}
void main()
{
cnt=0;
while(scanf("%d",&tar)!=EOF)
{
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[j]=0;
for(i=1;i<MAX;i++)
map=1,used=0,nu=0,d=0,n=0;
while(1)
{
scanf("%d %d",&a,&b);
if(a==0&&b==0)
break;
map[a]=1,map[a]=1;
}
d[1]=1;
for(i=1;i<MAX;i++)
{
for(j=1,t=0;j<MAX;j++)
{
if(d[j]&&!used[j])
{
t=j;
break;
}
}
used[t]=1;
for(j=1;j<MAX;j++)
if(map[t][j])
d[j]=1,p[j][n[j]++]=t;
}
for(i=1;i<MAX;i++)
used=0;
printf("CASE %d:\n",++cnt);
count=0,tmp=0;
dfs(tar);
for(i=1;i<MAX;i++)
if(nu>0)
qsort(next,nu[i],sizeof(int),presort);
dfs2(1);
printf("There are %d routes from the firestation to streetcorner %d.\n",count,tar);
}
}
[/cpp]
can anyone give me more special cases?? Thanks
The following is my code(i will appreciate very much if u can point out my mistakes):
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define MAX 22
int i,j,k,t,m,cnt,tar,num,count,a,b,tmp,map[MAX][MAX],n[MAX],p[MAX][MAX],ans[MAX];
int next[MAX][MAX],nu[MAX];
bool used[MAX],l,d[MAX];
void dfs2(int x)
{
int e,f;
used[x]=1;
ans[tmp++]=x;
if(x==tar)
{
for(e=0;e<tmp;e++)
{
if(e>0)
printf(" ");
printf("%d",ans[e]);
}
printf("\n");
tmp;
used[x]=0;
count++;
return ;
}
for(e=0;e<nu[x];e++)
{
if(!used[next[x][e]])
dfs2(next[x][e]);
}
tmp;
used[x]=0;
}
void dfs(int x)
{
int e,f,g;
used[x]=1;
if(x==1)
{
used[x]=0;
return;
}
for(e=0;e<n[x];e++)
{
if(!used[p[x][e]])
{
for(f=0,g=0;f<nu[p[x][e]];f++)
{
if(next[p[x][e]][f]==x)
{
g=1;
break;
}
}
if(g==0)
{
next[p[x][e]][nu[p[x][e]]++]=x;
dfs(p[x][e]);
}
}
}
used[x]=0;
}
int presort(const void *m1, const void *m2)
{
return *((int*)m1)*((int*)m2);
}
void main()
{
cnt=0;
while(scanf("%d",&tar)!=EOF)
{
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
map[j]=0;
for(i=1;i<MAX;i++)
map=1,used=0,nu=0,d=0,n=0;
while(1)
{
scanf("%d %d",&a,&b);
if(a==0&&b==0)
break;
map[a]=1,map[a]=1;
}
d[1]=1;
for(i=1;i<MAX;i++)
{
for(j=1,t=0;j<MAX;j++)
{
if(d[j]&&!used[j])
{
t=j;
break;
}
}
used[t]=1;
for(j=1;j<MAX;j++)
if(map[t][j])
d[j]=1,p[j][n[j]++]=t;
}
for(i=1;i<MAX;i++)
used=0;
printf("CASE %d:\n",++cnt);
count=0,tmp=0;
dfs(tar);
for(i=1;i<MAX;i++)
if(nu>0)
qsort(next,nu[i],sizeof(int),presort);
dfs2(1);
printf("There are %d routes from the firestation to streetcorner %d.\n",count,tar);
}
}
[/cpp]