539 - The Settlers of Catan
Moderator: Board moderators
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.
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]
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]
Last edited by russoue on Thu May 02, 2002 12:30 pm, edited 1 time in total.
>>>>>>>>>>>>
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.....
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.....
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.
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
And yet my memories still shine
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
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]
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]
-
- Learning poster
- Posts: 76
- Joined: Thu Mar 13, 2003 5:12 am
- Location: Russia
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
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
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
-
- 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....
can anybody tell why wa.. i know backtrackin is quite okay....
here's my code....
Code: Select all
Last edited by yogeshgo05 on Sun Feb 11, 2007 8:01 pm, edited 1 time in total.
There is a thread on this problem already.. plz use old thread to post..
I think these lines are located at a wrong place..
I think these lines are located at a wrong place..
Code: Select all
(*count)++;
...
...
v.push_back((*count));
(*count)--;
-
- New poster
- Posts: 47
- Joined: Sun Nov 27, 2005 12:43 pm
Last edited by yogeshgo05 on Sun Feb 11, 2007 8:01 pm, edited 1 time in total.
Try this test case. You'll know why WA.
The answer should be 2.
ADD: Don't forget removing your code after AC.
Code: Select all
2 2
0 1
1 0
0 0
ADD: Don't forget removing your code after AC.
-
- New poster
- Posts: 47
- Joined: Sun Nov 27, 2005 12:43 pm
-
- 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
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!!
Location: In front of a x86 machine So...you never know may be beside you!!
-
- 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.