Page 1 of 2

539 - The Settlers of Catan

Posted: Sun Apr 07, 2002 11:33 am
by russoue
Can anyone tell me what is the problem with my code? I think I got it right but am getting WA.
Please I need help.
Thanks in advance


[c]#include <stdio.h>

int n, m, max;
int matrix[30][30];
int not_visited[30];
void dfsbt(int, int);

int main(void)
{
register int i, j;
int from, to;


scanf("%d %d", &n, &m);
while(n || m) {
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
matrix[j] = 0;
}
not_visited = 1;
}

for(i = 0; i < m; i++) {
scanf("%d %d", &from, &to);
matrix[from][to] = matrix[to][from] = 1;
}

max = 0;
for(i = 0; i < n; i++) {
if(not_visited) {
dfsbt(i, 0);
}
}
printf("%dn", max);
scanf("%d %d", &n, &m);
}

return 0;
}

void dfsbt(int node, int length)
{
register int i;

not_visited[node] = 0;
if(length > max)
max = length;

for(i = 0; i < n; i++) {
if(matrix[node]) {
matrix[node] = matrix[node] = 0;
dfsbt(i, length + 1);
matrix[node] = matrix[node] = 1;
}
}
}[/c]

>>>>>>>>>>>>

Posted: Tue Apr 09, 2002 10:50 pm
by chang
U forget to print '\n'....u print 'n'
another matter, i used dfs taking each node as starting node....I can't remember why i used so...if u get WA, u may modify it.....

Posted: Wed Apr 10, 2002 7:29 pm
by russoue
Thanks for your reply.
Actually I was printing "\n" in my code but for unknown reason the '\' is not showing up here.

Solution

Posted: Mon Aug 05, 2002 3:30 pm
by obayashi
I've modified your code a little and merged with my code, then got AC...

The problem with your code lies in the varible "not_visited".

There's no need to use this varible to mark the node visited.

The problems just has something to do with the EDGE not the NODE.

So to mark the node is not reasonable.

Just leave out it and you will certainly get AC.

Good luck.

p.s. I've learned a lot from your code. Thanks indeed.

539 what's the idea?

Posted: Sat Jan 31, 2004 11:59 am
by New(User)
what's the idea for this problem ?

i tried to do a modified dfs starting from each node and memorize the longest distance but i get time limit exceeded..

here's my code:
[pascal]
program settlers;
var mat,A:array [0..50,0..50] of integer;
max:integer;
n:integer;
procedure DF(i,l:integer);
var j:integer;
begin
if (l > max) then max:=L;
for j:=1 to N do
if A[i,j]=1 then begin
A[i,j]:=0;
A[j,i]:=0;
df(j,l+1);
A[i,j]:=1;
A[j,i]:=1;
end;
end;
procedure Solve;
var i:integer;
begin
max:=0;
for i:=0 to N do
begin
A:=mat;
DF(i,0);
end;
writeln(output,max);
end;
procedure fA(m:integer);
var x,y,i:integer;
begin
for i:=1 to m do
begin
readln(input,x,y);
mat[x,y]:=1;
mat[y,x]:=1;
end;
Solve;
end;
procedure fB;
var m:integer;
begin
readln(input,n,m);
while not ((m=0) and (n=0)) do
begin
fA(m);
readln(input,n,m);
end;
end;
begin
fB;
end.
[/pascal]

Posted: Wed Feb 02, 2005 8:14 pm
by Experimenter
i can't believe i got accepted using brute force. :lol: :o :lol: what a bullshit. :D :o :o :lol:

Posted: Tue Feb 08, 2005 1:24 pm
by Eduard
Hello New(User)
You have some mistakes in your code.
AT first after reading make n:=n-1.Then clean your mat array after each test case.In procedure DF make j:=0 to n do.
And you will get AC.If you will have WA tell me.
Eduard

539 why wa ..plz help

Posted: Tue Feb 06, 2007 6:22 am
by yogeshgo05
hell guys ..
can anybody tell why wa.. i know backtrackin is quite okay....
here's my code....

Posted: Tue Feb 06, 2007 8:19 am
by helloneo
There is a thread on this problem already.. plz use old thread to post..

I think these lines are located at a wrong place..

Code: Select all

(*count)++; 
...
...
v.push_back((*count)); 
(*count)--; 

Posted: Fri Feb 09, 2007 10:17 pm
by yogeshgo05
i have modified the code a bit i guess...
plz tell me why wa....

Posted: Sat Feb 10, 2007 7:30 pm
by rio
Try this test case. You'll know why WA.

Code: Select all

2 2
0 1
1 0
0 0
The answer should be 2.

ADD: Don't forget removing your code after AC.

Posted: Tue Feb 13, 2007 7:51 am
by soyoja
Additonal comment about rio's post. =)

It's an undirectional graph. threrfore, 0 -> 1 is same as 1 -> 0.
Good luck.

Posted: Tue Feb 13, 2007 5:24 pm
by yogeshgo05
hey that's rite...

then rio means

0 1
1 0

if the ans is 2
then
are two different undirected edges.....
that means there can many edges b/w the same two nodes....
so that resulting in first bactracking b/w the nodes...

Re: 539 why wa ..plz help

Posted: Tue Mar 31, 2009 12:46 pm
by rifayat samee_du
Hello rio??
there is no input like
2 2
0 1
1 0

Re: 539 why wa ..plz help

Posted: Fri Oct 19, 2012 3:27 pm
by Mukit Chowdhury
got WA !!! please help me !!! give me some sample input !!!

Code: Select all

Deleted after accepted !!!!!!