## 539 - The Settlers of Catan

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

Moderator: Board moderators

russoue
New poster
Posts: 2
Joined: Sun Apr 07, 2002 2:00 am

### 539 - The Settlers of Catan

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.

[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]
Last edited by russoue on Thu May 02, 2002 12:30 pm, edited 1 time in total.

chang
New poster
Posts: 16
Joined: Wed Jan 16, 2002 2:00 am

### >>>>>>>>>>>>

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.....

russoue
New poster
Posts: 2
Joined: Sun Apr 07, 2002 2:00 am
Actually I was printing "\n" in my code but for unknown reason the '\' is not showing up here.

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

### Solution

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.
Time makes a fool of memory
And yet my memories still shine

New(User)
New poster
Posts: 3
Joined: Sat Jan 31, 2004 11:01 am

### 539 what's the idea?

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
mat[x,y]:=1;
mat[y,x]:=1;
end;
Solve;
end;
procedure fB;
var m:integer;
begin
while not ((m=0) and (n=0)) do
begin
fA(m);
end;
end;
begin
fB;
end.
[/pascal]

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia
i can't believe i got accepted using brute force. what a bullshit.
it would be great if you replied this post. really.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
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
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

### 539 why wa ..plz help

hell guys ..
can anybody tell why wa.. i know backtrackin is quite okay....
here's my code....
Last edited by yogeshgo05 on Sun Feb 11, 2007 8:01 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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)--;
``````

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm
i have modified the code a bit i guess...
plz tell me why wa....
Last edited by yogeshgo05 on Sun Feb 11, 2007 8:01 pm, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

It's an undirectional graph. threrfore, 0 -> 1 is same as 1 -> 0.
Good luck.
I love Problem Solving!!!

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm
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...

rifayat samee_du
New poster
Posts: 9
Joined: Tue Jul 11, 2006 8:44 am
Location: Beside you........

### Re: 539 why wa ..plz help

Hello rio??
there is no input like
2 2
0 1
1 0
Name : Sanzee
Location: In front of a x86 machine So...you never know may be beside you!!

Mukit Chowdhury
Learning poster
Posts: 99
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 539 why wa ..plz help

got WA !!! please help me !!! give me some sample input !!!

Code: Select all

``````Deleted after accepted !!!!!!
``````
Last edited by Mukit Chowdhury on Sat Oct 20, 2012 4:35 am, edited 1 time in total.