677 - All Walks of length "n" from the first node

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

677 - All Walks of length "n" from the first node

Post by yahoo »

Code: Select all

#include<stdio.h>
#define N 20
int n,d,time,a[N][N],b[N],path;
char color[N];
void dfs(int s)
{
	int i;
	if(time==(d+1))
	{
		path++;
		printf("{");
		for(i=0;i<=d;i++)
		{
			if(i) printf(",");
			printf("%d",b[i]+1);
		}
		printf("}\n");
		return ;
	}
	for(i=0;i<n;i++)
		if(color[i]=='w' && a[s][i])
		{
			color[i]='g';
			b[time++]=i;
			dfs(i);
			b[--time]=0;
			color[i]='w';
		}
}

main()
{
	freopen("c:\\in.txt","r",stdin);
	int cases=0,i,j;
	while(1)
	{
		if(cases) scanf("%d",&d);
		if(scanf("%d%d",&n,&d)==EOF) break;
		if(cases) printf("\n");
		cases++;
		for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&a[i][j]);
		for(i=0;i<n;i++) color[i]='w'; time=path=0;
		time=1;
		color[0]='g';
		dfs(0);
		if(path==0) printf("no walk of length %d\n",d);
	}
	return 0;
}
here goes my code..
i think it's not hard to read and realize..
but why wa for just a simple problem..
dominik, tomal bhai .. and to all please help..
i am very crazy to solve it.. by just dfs..
please helpp......
drowning anupam.... :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: [/b]

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

i think your terminating condition is not right.
i can remember that i terminated when i expected -9999 but got something else.

it might help.

thanx
-sohel

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

what a problem

Post by anupam »


bhai,,
i still today can't understand the terminating condition..
yahoo and i are the same..
i used scanf("%d",&d);
if(d!=-9999) break;
till today it's wa..
what happened..
please tell me in a larger resolution...
---
you can mail me privately.. via acm or abrbuet@yahoo.com
please help.. i am just trying all the stones to solve such a simple problem/........ :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Location: Chittagong,Bangladesh
Contact:

677:What is input terminate condition?

Post by erfan »

What is the terminate condition of it i cannot realize.
I terminate input just :

Code: Select all

if(flag) scanf("%ld",&d);
      if(scanf("%ld%ld",&n,&d)!=2) break;
If it is right may my algorithm is wrong.Pls provide some critical input/output to judge my code.
Pls anybody help me.

ei01036
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am

Post by ei01036 »

As i understand, the input termitation condition is related with that -9999. When it doen's exists, you can be sure you're not between test cases, therefore you're ate the end.

felix_halim
New poster
Posts: 2
Joined: Sat Sep 21, 2002 12:00 pm
Location: Indonesia
Contact:

Post by felix_halim »

Maybe you forgot to print "no walk of length n" if the path doesn't exist :P

Don't forget! n is variable!
You should printf("no walk of length %d\n",n);
instead of puts("no walk of length n");
Felix Halim

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Re: what's wrong with 677

Post by anupam »

[quote="yahoo"]

Code: Select all

		if(path==0) printf("no walk of length %d\n",d);
From the above code segment you can feel that
I have checked that..
But still wa...
--
Anupam
"Everything should be made simple, but not always simpler"

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm

Post by dvntae »

it's funny 2 find out that ur program is completely perfect (even no problem with the -9999), the only reason why it's WA is ur using the wrong bracket. replace the bracket: "{}" with "()" and done...

next time, use glasses. u maybe need 1. =) hehhehe..

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

:D :D I already use one....
Yahoo also uses.... :D
Thank you for your advice..
Better be a doctor....
--
Anupam
"Everything should be made simple, but not always simpler"

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

very simple

Post by rushel »

I was having the same problem.
but when i read the following line from the problem carefully i got AC :)

the line:
Separate the output of the different cases by a blank line.

if( N == -9999 ) {
cout << endl;
continue;
}


:D

sacrebar
New poster
Posts: 2
Joined: Wed Aug 10, 2005 11:39 pm
Location: Mexico

677 Why WA??? please help me

Post by sacrebar »

It's my code, please help me, I don`t understand my error
Last edited by sacrebar on Wed Sep 07, 2005 5:43 pm, edited 1 time in total.

sacrebar
New poster
Posts: 2
Joined: Wed Aug 10, 2005 11:39 pm
Location: Mexico

Re: 677 Why WA??? please help me

Post by sacrebar »

El codigo esta bien solo le falta un vector de visitas antes de llamar ala recursi

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

Post by Dominik Michniewski »

Sacrebar:
Please translate your message into englisch - it could be useful for other people, which will be search for hints :)
and if your code is accepted, remove your code :)


Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Post by sabir »

i am getting WA in this code.plz help.

Code: Select all

Deleted
Last edited by sabir on Mon Oct 29, 2007 7:17 am, edited 1 time in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Post by sapnil »

To sabir,
you may miss this line.

Code: Select all

In case there are not walks of length n, just print `no walk of length n'
Thanks
Keep posting
Sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

Post Reply

Return to “Volume 6 (600-699)”