## 208 - Firetruck

Moderator: Board moderators

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
The same thing has dont to me
cant cross the prob:
TLE

/* @JUDGE_ID: XXXXX 208 C++ */
#include <stdio.h>

int TR;

void FR( int a,int n,int corner,int route[],int RM[22][22])
{
int i, j;

if (a == n)
{
TR++;

printf("%d", route[0]);
for (i=1; i < corner; i++)
{
printf("%4d", route);
}

printf("\n");
return;
}

for (i=0; i<22; i++)
{
if (RM[a])
{
for (j=0; j<corner; j++)
{
if(route[j] == i)
break;
}

if (j == corner)
{
route[corner] = i;

FR(i, n, corner+1,route, RM);
}
}
}
}

void main()
{
int x, y, n, c, route[22], RM[22][22];

for(c=1;scanf("%d", &n)==1;c++)
{
for (x=0; x<22; x++)
for (y=0; y<22; y++)
RM[x][y] = 0;

while (scanf("%d %d", &x, &y))
{
if(!x && !y)
break;

RM[x][y] = 1;
RM[y][x] = 1;

}

printf("CASE %d:\n", c);
route[0] = 1;
TR = 0;
FR(1, n, 1, route, RM);

printf("There are %d routes from the firestation ", TR);
printf("to streetcorner %d.\n", n);
}

}
/*@END_OF_SOURCE_CODE */

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I got TLE too with this problem at first. my friend gave me some hints.
first, use floyd or warshall to determine whether the node is reachable to the destination while using dfs... then i got AC...
I think this is enough if you actually bother to read the post..

LTH
New poster
Posts: 12
Joined: Fri Feb 08, 2002 2:00 am
Location: Taiwan
Contact:
i didnt mean that i got TLE.
I have done what was discussed and I got a 0.002 sec WA....
i dont know why....

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:

### 208

Can any body give me some input and output for 208(firetruc)
problem?
thanx

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am

### 208 Why Time Limit Exceeded

This is My code

#include<stdio.h>

int FireCorner;
int StreetCornerS=1,StreetCornerD=1;
int Path[1000];
int mutex,mutex1;
int max=0,i,j,PathNum;

void DFS(int u,int z)
{
int k=0;

Path[z]=u;
z++;
for(int j=1;j<=max;j++)
{
if(u==FireCorner)
break;
{
mutex=0;
for(k=1;k<z;k++)
{
if(Path[k]==j)
{
mutex=1;
break;
}
}
if(mutex!=1)
{
mutex1=1;
DFS(j,z);
}
}
}
if(mutex1==1&&Path[z-1]==FireCorner)
{
PathNum++;
for(int k1=1;k1<z;k1++)
printf("%d ",Path[k1]);
printf("\n");
}
}

void main()
{

int cas=0;
while(1==scanf("%d",&FireCorner))
{ cas++;
if(FireCorner<=0||FireCorner>=21)
break;
while(StreetCornerS!=0&&StreetCornerD!=0)
{
scanf("%d %d",&StreetCornerS,&StreetCornerD);
if(max<StreetCornerS)
max=StreetCornerS;
if(max<StreetCornerD)
max=StreetCornerD;
}
printf("CASE %d:\n",cas);
DFS(1,1);
StreetCornerS=1;
StreetCornerD=1;
for(i=1;i<=max;i++)
for(j=1;j<=max;j++)
i=1;
max=0;
while(Path!=0)
{
Path=0;
i++;
}
printf("There are %d routs from the firestation to streetcorner %d.\n",PathNum,FireCorner);
PathNum=0;
}
}

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
I haven't gone through your code thoroughly, but from what it looks, I think you are just running a plain dfs() and it is likely to get TLE..

... You can prune at certain nodes once you know that going through that node will not lead you to the destination.

.. I used FW to find those nodes and then applied DFS() and it passed TL.

Hope it helps.

efr_shovo
New poster
Posts: 38
Joined: Wed Sep 22, 2004 9:09 am
How Can you use FW .Cozz.. There is No Weight. And What Is Prune.

Please Describe the Sentence That you say-----"... You can prune at certain nodes once you know that going through that node will not lead you to the destination."

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
LTH wrote:i didnt mean that i got TLE.
I have done what was discussed and I got a 0.002 sec WA....
i dont know why....
I also got WA. dunno why. Can anybody give some I/O?
Impossible is Nothing.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
i got AC. stupid mistake
Impossible is Nothing.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Hi Fellows,

Just for your information, there are some more test cases:

Input:

Code: Select all

``````6
1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
0 0
4
2 3
3 4
5 1
1 6
7 8
8 9
2 5
5 7
3 1
1 8
4 6
6 9
0 0
20
1 2
1 5
1 6
2 5
4 12
4 13
4 14
5 9
5 14
5 17
6 7
6 8
7 17
8 16
9 12
9 13
10 14
10 15
11 16
11 17
13 18
14 20
15 16
15 17
16 19
17 19
18 20
19 20
0 0
2
1 2
1 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 12
4 13
4 14
4 15
4 16
4 17
4 18
4 19
4 20
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
10 11
10 12
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 20
11 12
11 13
11 14
11 15
11 16
11 17
11 18
11 19
11 20
12 13
12 14
12 15
12 16
12 17
12 18
12 19
12 20
13 14
13 15
13 16
13 17
13 18
13 19
13 20
14 15
14 16
14 17
14 18
14 19
14 20
15 16
15 17
15 18
15 19
15 20
16 17
16 18
16 19
16 20
17 18
17 19
17 20
18 19
18 20
19 20
0 0
4
1 2
1 5
2 3
5 3
3 4
5 6
5 7
5 8
5 9
5 10
5 11
5 12
5 13
5 14
5 15
5 16
5 17
5 18
5 19
5 20
6 7
6 8
6 9
6 10
6 11
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 19
6 20
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 16
7 17
7 18
7 19
7 20
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20
9 10
9 11
9 12
9 13
9 14
9 15
9 16
9 17
9 18
9 19
9 20
10 11
10 12
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 20
11 12
11 13
11 14
11 15
11 16
11 17
11 18
11 19
11 20
12 13
12 14
12 15
12 16
12 17
12 18
12 19
12 20
13 14
13 15
13 16
13 17
13 18
13 19
13 20
14 15
14 16
14 17
14 18
14 19
14 20
15 16
15 17
15 18
15 19
15 20
16 17
16 18
16 19
16 20
17 18
17 19
17 20
18 19
18 20
19 20
0 0
``````
output:

Code: Select all

``````CASE 1:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
There are 7 routes from the firestation to streetcorner 6.
CASE 2:
1 3 2 5 7 8 9 6 4
1 3 4
1 5 2 3 4
1 5 7 8 9 6 4
1 6 4
1 6 9 8 7 5 2 3 4
1 8 7 5 2 3 4
1 8 9 6 4
There are 8 routes from the firestation to streetcorner 4.
CASE 3:
1 2 5 9 12 4 13 18 20
1 2 5 9 12 4 14 10 15 16 8 6 7 17 19 20
1 2 5 9 12 4 14 10 15 16 11 17 19 20
1 2 5 9 12 4 14 10 15 16 19 20
1 2 5 9 12 4 14 10 15 17 7 6 8 16 19 20
1 2 5 9 12 4 14 10 15 17 11 16 19 20
1 2 5 9 12 4 14 10 15 17 19 20
1 2 5 9 12 4 14 20
1 2 5 9 13 4 14 10 15 16 8 6 7 17 19 20
1 2 5 9 13 4 14 10 15 16 11 17 19 20
1 2 5 9 13 4 14 10 15 16 19 20
1 2 5 9 13 4 14 10 15 17 7 6 8 16 19 20
1 2 5 9 13 4 14 10 15 17 11 16 19 20
1 2 5 9 13 4 14 10 15 17 19 20
1 2 5 9 13 4 14 20
1 2 5 9 13 18 20
1 2 5 14 4 12 9 13 18 20
1 2 5 14 4 13 18 20
1 2 5 14 10 15 16 8 6 7 17 19 20
1 2 5 14 10 15 16 11 17 19 20
1 2 5 14 10 15 16 19 20
1 2 5 14 10 15 17 7 6 8 16 19 20
1 2 5 14 10 15 17 11 16 19 20
1 2 5 14 10 15 17 19 20
1 2 5 14 20
1 2 5 17 7 6 8 16 15 10 14 4 12 9 13 18 20
1 2 5 17 7 6 8 16 15 10 14 4 13 18 20
1 2 5 17 7 6 8 16 15 10 14 20
1 2 5 17 7 6 8 16 19 20
1 2 5 17 11 16 15 10 14 4 12 9 13 18 20
1 2 5 17 11 16 15 10 14 4 13 18 20
1 2 5 17 11 16 15 10 14 20
1 2 5 17 11 16 19 20
1 2 5 17 15 10 14 4 12 9 13 18 20
1 2 5 17 15 10 14 4 13 18 20
1 2 5 17 15 10 14 20
1 2 5 17 15 16 19 20
1 2 5 17 19 16 15 10 14 4 12 9 13 18 20
1 2 5 17 19 16 15 10 14 4 13 18 20
1 2 5 17 19 16 15 10 14 20
1 2 5 17 19 20
1 5 9 12 4 13 18 20
1 5 9 12 4 14 10 15 16 8 6 7 17 19 20
1 5 9 12 4 14 10 15 16 11 17 19 20
1 5 9 12 4 14 10 15 16 19 20
1 5 9 12 4 14 10 15 17 7 6 8 16 19 20
1 5 9 12 4 14 10 15 17 11 16 19 20
1 5 9 12 4 14 10 15 17 19 20
1 5 9 12 4 14 20
1 5 9 13 4 14 10 15 16 8 6 7 17 19 20
1 5 9 13 4 14 10 15 16 11 17 19 20
1 5 9 13 4 14 10 15 16 19 20
1 5 9 13 4 14 10 15 17 7 6 8 16 19 20
1 5 9 13 4 14 10 15 17 11 16 19 20
1 5 9 13 4 14 10 15 17 19 20
1 5 9 13 4 14 20
1 5 9 13 18 20
1 5 14 4 12 9 13 18 20
1 5 14 4 13 18 20
1 5 14 10 15 16 8 6 7 17 19 20
1 5 14 10 15 16 11 17 19 20
1 5 14 10 15 16 19 20
1 5 14 10 15 17 7 6 8 16 19 20
1 5 14 10 15 17 11 16 19 20
1 5 14 10 15 17 19 20
1 5 14 20
1 5 17 7 6 8 16 15 10 14 4 12 9 13 18 20
1 5 17 7 6 8 16 15 10 14 4 13 18 20
1 5 17 7 6 8 16 15 10 14 20
1 5 17 7 6 8 16 19 20
1 5 17 11 16 15 10 14 4 12 9 13 18 20
1 5 17 11 16 15 10 14 4 13 18 20
1 5 17 11 16 15 10 14 20
1 5 17 11 16 19 20
1 5 17 15 10 14 4 12 9 13 18 20
1 5 17 15 10 14 4 13 18 20
1 5 17 15 10 14 20
1 5 17 15 16 19 20
1 5 17 19 16 15 10 14 4 12 9 13 18 20
1 5 17 19 16 15 10 14 4 13 18 20
1 5 17 19 16 15 10 14 20
1 5 17 19 20
1 6 7 17 5 9 12 4 13 18 20
1 6 7 17 5 9 12 4 14 10 15 16 19 20
1 6 7 17 5 9 12 4 14 20
1 6 7 17 5 9 13 4 14 10 15 16 19 20
1 6 7 17 5 9 13 4 14 20
1 6 7 17 5 9 13 18 20
1 6 7 17 5 14 4 12 9 13 18 20
1 6 7 17 5 14 4 13 18 20
1 6 7 17 5 14 10 15 16 19 20
1 6 7 17 5 14 20
1 6 7 17 11 16 15 10 14 4 12 9 13 18 20
1 6 7 17 11 16 15 10 14 4 13 18 20
1 6 7 17 11 16 15 10 14 5 9 12 4 13 18 20
1 6 7 17 11 16 15 10 14 5 9 13 18 20
1 6 7 17 11 16 15 10 14 20
1 6 7 17 11 16 19 20
1 6 7 17 15 10 14 4 12 9 13 18 20
1 6 7 17 15 10 14 4 13 18 20
1 6 7 17 15 10 14 5 9 12 4 13 18 20
1 6 7 17 15 10 14 5 9 13 18 20
1 6 7 17 15 10 14 20
1 6 7 17 15 16 19 20
1 6 7 17 19 16 15 10 14 4 12 9 13 18 20
1 6 7 17 19 16 15 10 14 4 13 18 20
1 6 7 17 19 16 15 10 14 5 9 12 4 13 18 20
1 6 7 17 19 16 15 10 14 5 9 13 18 20
1 6 7 17 19 16 15 10 14 20
1 6 7 17 19 20
1 6 8 16 11 17 5 9 12 4 13 18 20
1 6 8 16 11 17 5 9 12 4 14 20
1 6 8 16 11 17 5 9 13 4 14 20
1 6 8 16 11 17 5 9 13 18 20
1 6 8 16 11 17 5 14 4 12 9 13 18 20
1 6 8 16 11 17 5 14 4 13 18 20
1 6 8 16 11 17 5 14 20
1 6 8 16 11 17 15 10 14 4 12 9 13 18 20
1 6 8 16 11 17 15 10 14 4 13 18 20
1 6 8 16 11 17 15 10 14 5 9 12 4 13 18 20
1 6 8 16 11 17 15 10 14 5 9 13 18 20
1 6 8 16 11 17 15 10 14 20
1 6 8 16 11 17 19 20
1 6 8 16 15 10 14 4 12 9 5 17 19 20
1 6 8 16 15 10 14 4 12 9 13 18 20
1 6 8 16 15 10 14 4 13 9 5 17 19 20
1 6 8 16 15 10 14 4 13 18 20
1 6 8 16 15 10 14 5 9 12 4 13 18 20
1 6 8 16 15 10 14 5 9 13 18 20
1 6 8 16 15 10 14 5 17 19 20
1 6 8 16 15 10 14 20
1 6 8 16 15 17 5 9 12 4 13 18 20
1 6 8 16 15 17 5 9 12 4 14 20
1 6 8 16 15 17 5 9 13 4 14 20
1 6 8 16 15 17 5 9 13 18 20
1 6 8 16 15 17 5 14 4 12 9 13 18 20
1 6 8 16 15 17 5 14 4 13 18 20
1 6 8 16 15 17 5 14 20
1 6 8 16 15 17 19 20
1 6 8 16 19 17 5 9 12 4 13 18 20
1 6 8 16 19 17 5 9 12 4 14 20
1 6 8 16 19 17 5 9 13 4 14 20
1 6 8 16 19 17 5 9 13 18 20
1 6 8 16 19 17 5 14 4 12 9 13 18 20
1 6 8 16 19 17 5 14 4 13 18 20
1 6 8 16 19 17 5 14 20
1 6 8 16 19 17 15 10 14 4 12 9 13 18 20
1 6 8 16 19 17 15 10 14 4 13 18 20
1 6 8 16 19 17 15 10 14 5 9 12 4 13 18 20
1 6 8 16 19 17 15 10 14 5 9 13 18 20
1 6 8 16 19 17 15 10 14 20
1 6 8 16 19 20
There are 152 routes from the firestation to streetcorner 20.
CASE 4:
1 2
There are 1 routes from the firestation to streetcorner 2.
CASE 5:
1 2 3 4
1 5 3 4
There are 2 routes from the firestation to streetcorner 4.
``````
I found the test cases interesting because my AC program that ran in 0.004 sec on judge actually TLE on my computer (I waited too long I gave up, but its a lot more than 10 sec.). I posed them so you can check whether your program will pass TLE with these input.

I wrote another program that computes the result of the above input in about 8sec., and that one actually ran for 7 sec. (AC) on judge.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Floyd-Warshall And Then Backtracking With Some Prunning

Efr_shovo,

Have you already got ACC on problem 208 ?
I am asking because I can see your last post in this

If you haven't solved it yet - here are the answers

1) Use Floyd-Warshall by first defining some weights yourself.
In case there's an edge between two nodes n1 and n2 just
define weight[n1][n2] = weight[n2][n1] = 1.
If no edge exists between n1 and n2 just define
weight[n1][n2] = weight[n2][n1] = INFINITE
( INFINITE could be some constant like -1000000 for example,
but the exact value of this constant is not important ).

2) Prunning means that when we do some backtracking procedure
we just do not follow certain subtrees in the backtracking recursion
tree. We call this prunning the backtracking tree or just prunning.
In our case we should do it as follows. Say our route ( path )
has started at node 1. And say also that we have just reached node N.
Say also that our target node is T. So ... our current node is N.
Well, then in our backtracking procedure the first thing we should do
is to check if dist[N][T]==INFINITE. If so then it makes no sense
to continue with that branch ( subtree ) of our backtracking
procedure as we know for sure that there is no route(path)
from N to T. Here by dist[][] I have denoted the distance
matrix which has been initialized with correct values by
the Floyd-Warshall algorithm. If dist[n1][n2]==INFINITE after
we have applied the Floyd-Warshall algorithm this means there's
no route(path) in the graph between the nodes n1 and n2.

is still working on this problem.

I can see it has been solved till now by just 440 people. And it
is not so difficult actually, if we follow the idea which Sohel
has posted above.

arbiter_tl
New poster
Posts: 2
Joined: Sat Jun 03, 2006 11:49 am

### 208 HELP PLZ

I get time limit exceed, but I'm sure that algorithm is quiet fast. I guess problem is in input section. Can anyone help plz? This is my first problem to be solved, and I don't know the input standarts for the Judge system

Code: Select all

``````#include <iostream.h>
#include <stdio.h>

struct {
int taint;
} corner[20];

int paths;
int path[20];
int npath;

void print_paths(int a, int b) {
if (corner[a].taint) return;
if (a==b) {
for (int i=0; i<npath; i++)
printf("%-4d", path[i]+1);
printf("%d\n", b+1);
paths++;
return;
}
corner[a].taint = 1;
path[npath++] = a;
npath--;
corner[a].taint = 0;
}

int main() {
int dest, count=1;
while (cin >> dest) {
dest--;
int i;
for (i=0; i<20; i++) corner[i].taint = corner[i].nadj = 0;
int a, b;
while (cin >> a >> b && a && b) {
a--, b--;
}
paths = npath = 0;
cout << "CASE " << count++ << ":" << endl;
print_paths(0, dest);
if (paths == 1)
cout << "There is 1 route from the firestation to streetcorner " <<
dest+1 << "." << endl;
else
cout << "There are " << paths <<
" routes from the firestation to streetcorner " << dest+1 << "." <<
endl;
}
return 0;
}
``````

arbiter_tl
New poster
Posts: 2
Joined: Sat Jun 03, 2006 11:49 am
http://acm.uva.es/p/v2/208.html - here is the link for the problem itself

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
http://online-judge.uva.es/board/viewtopic.php?t=6581

i.kokan
New poster
Posts: 1
Joined: Fri Oct 06, 2006 2:00 am

### 208 - WA

Can someone tell me what's wrong with my solution? Thanks in advance.

Code: Select all

``````/* acm.uva.es */

#include <stdio.h>
#include <stdlib.h>

int N, length, was[21], array[21], list[21][21], poss[21], cnt;
unsigned long sol;

int cmp (const void *a, const void *b) {
if (* (const int *) a > * (const int *) b)
return 1;

return -1;
}

void recursion (int id) {
int i, remember_sol;

array[++length] = id;
was[id] = 1;

if (id == N) {
sol++;

printf ("1");

for (i = 2; i <= length; i++)
printf (" %d", array[i]);

printf ("\n");
}
else {
remember_sol = sol;

for (i = 1; i <= list[id][0]; i++)
if (was[list[id][i]] == 0 && poss[list[id][i]] == 1)
recursion (list[id][i]);

if (remember_sol == sol)
poss[id] = 0;
}

length--;
was[id] = 0;

return;
}

int main (void) {
int a, b;

while (scanf ("%d", &N) != EOF) {
cnt++;
length = sol = 0;

for (a = 1; a <= 20; a++) {
was[a] = 0;
list[a][0] = 0;
poss[a] = 1;
}

while (1) {
scanf ("%d %d", &a, &b);

if (a == 0 && b == 0)
break;

list[a][0]++;
list[a][list[a][0]] = b;

list[b][0]++;
list[b][list[b][0]] = a;
}

for (a = 1; a <= 20; a++)
qsort (&list[a][1], list[a][0], sizeof (int), cmp);

printf ("CASE %d:\n", cnt);

recursion (1);

printf ("There are %lu routes from the firestation to streetcorner %d.\n", sol, N);
}

return 0;
}
``````