Page 1 of 4
352 The Seasonal War
Posted: Wed Jun 12, 2002 4:54 am
by Betovsky
hmm in this prob
this case
101
010
101
are 5 planes or only 1 plane?
Posted: Wed Jun 12, 2002 6:14 am
by Betovsky
dam to the samples it works great
but the judge keeps saying WA can some1 tell me whta wrong
[c]
#include <stdio.h>
#include <stdlib.h>
void init(void);
void check(int, int);
int a[27][27];
int main(){
int image=0;
int linha;
int n, k;
int i, j;
while(scanf("%d", &n) != EOF){
image++;
init();
k=0;
for(i=1;i<=n;i++){
scanf("%d", &linha);
for(j=1;j<=n;j++){
a[j]=linha%10;
linha=linha/10;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[j]==1){
k++;
a[j]=2;
check(i,j);
}
printf("Image number %d contains %d war eagles.\n", image, k);
}
return 0;
}
void init(){
int i,j;
for(i=0;i<27;i++)
for(j=0;j<27;j++)
a[j]=0;
}
void check(int is, int js){
int i,j;
for(i=is-1;i<=is+1;i++)
for(j=js-1;j<=js+1;j++)
if(a[j]==1){
a[j]=2;
check(i,j);
}
}
[/c]
thx... sorry for the trouble.
Posted: Wed Jun 12, 2002 7:34 pm
by Caesum
your only problem is the following code:
[c]
for(i=1;i<=n;i++){
scanf("%d", &linha);
for(j=1;j<=n;j++){
a[j]=linha%10;
linha=linha/10;
}
}
[/c]
use a char array, not an int, think about a 25 long string..... 111111111111111111 etc, it loses the precision you need.
Posted: Wed Jun 12, 2002 10:22 pm
by Betovsky
Gracias , my head was starting to disintegrates...
i was starting to think of throwing my self over a bridge.
352 - The Seasonal War
Posted: Thu Mar 20, 2003 12:40 am
by Derk
For some reason, my 352 keeps getting WA. It's virtually identical to other problems I've solved such as 572 and 260. I've thrown every piece of test input I can think at it. Tested boundary conditions, etc. Here's the input I'm working with and corresponding output:
5
10001
00000
00000
00000
10001
6
100100
001010
000000
110000
111000
010100
8
01100101
01000001
00011000
00000010
11000011
10100010
10000001
01100000
2
01
10
2
11
11
1
1
1
0
3
101
010
101
4
0000
0100
0001
0000
4
1000
0010
1000
0010
0
0
0
5
10101
01010
10101
01010
10101
And the output:
Image number 1 contains 4 war eagles.
Image number 2 contains 3 war eagles.
Image number 3 contains 6 war eagles.
Image number 4 contains 1 war eagles.
Image number 5 contains 1 war eagles.
Image number 6 contains 1 war eagles.
Image number 7 contains 0 war eagles.
Image number 8 contains 1 war eagles.
Image number 9 contains 2 war eagles.
Image number 10 contains 4 war eagles.
Image number 11 contains 0 war eagles.
Image number 12 contains 0 war eagles.
Image number 13 contains 0 war eagles.
Image number 14 contains 1 war eagles.
Is there some weird case that I'm just not considering? My array is well within the input size limit (I made it 50x50 just to test for large cases, and I initialize all elements to NULL).
If some suggested input from you all holds up, I'll post my program so you can see the algorithm I'm using.
Thanks![/quote]
Posted: Thu Mar 20, 2003 8:54 am
by Dominik Michniewski
I got the same output as yours and got Acc.
I use DFS to find number of war eagles on board and I use 25x25 board.
Maybe you have a small mistake in your code ?
Dominik
Hm
Posted: Thu Mar 20, 2003 10:37 am
by Derk
What is DFS?
Anyway, here's my code:
[c]/* @JUDGE_ID: xxxxxxx 352 C*/
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#define BUFFERSIZE 27
char buffer[BUFFERSIZE][BUFFERSIZE];
void check(int i, int j)
{
buffer[j]='0';
if(i > 0 && j > 0 && buffer[i-1][j-1] == '1')
check(i-1,j-1);
if(i > 0 && buffer[i-1][j] == '1')
check(i-1,j);
if(i > 0 && buffer[i-1][j+1] == '1')
check(i-1,j+1);
if(j > 0 && buffer[j-1] == '1')
check(i,j-1);
if(buffer[j+1] == '1')
check(i,j+1);
if(j > 0 && buffer[i+1][j-1] == '1')
check(i+1,j-1);
if(buffer[i+1][j] == '1')
check(i+1, j);
if(buffer[i+1][j+1] == '1')
check(i+1,j+1);
}
main()
{
int a,cnt=1,i,j,war;
#ifndef ONLINE_JUDGE
close (0); open ("352.in", O_RDONLY);
close (1); open ("352.out", O_WRONLY | O_CREAT, 0600);
#endif
while(gets(buffer[0]))
{
a = atoi(buffer[0]);
war = 0;
if (a != 0)
{
for(i=0;i<BUFFERSIZE;i++)
for(j=0;j<BUFFERSIZE;j++)
buffer[j] = 0x00;
for(i=0;i<a;i++)
gets(buffer);
for(i=0;i<BUFFERSIZE;i++)
for(j=0;j<BUFFERSIZE;j++)
if(buffer[j] == '1')
{
war++;
check(i,j);
}
}
printf("Image number %d contains %d war eagles.\n", cnt++, war);
}
}
/* @END_OF_SOURCE_CODE */[/c]
Posted: Thu Mar 20, 2003 12:34 pm
by Dominik Michniewski
DFS - Depth First Search
Your algorithm looks good
I use the same and I think, that I could say that it's kind of DFS...
Dominik
PS. Try to change
Code: Select all
for(i=0;i<BUFFERSIZE;i++)
for(j=0;j<BUFFERSIZE;j++)
if(buffer[i][j] == '1')
{
war++;
check(i,j);
}
to
Code: Select all
for(i=0;i<BUFFERSIZE-1;i++)
for(j=0;j<BUFFERSIZE-1;j++)
if(buffer[i][j] == '1')
{
war++;
check(i,j);
}
Posted: Thu Mar 20, 2003 1:04 pm
by Adrian Kuegel
Use scanf instead of gets, then you will get Accepted.
Posted: Thu Mar 20, 2003 1:23 pm
by Dominik Michniewski
That means, that at end of line are some additional spaces ?
I don't like such traps .... But Adrian has right - I use scanf too ...
Dominik
Cool
Posted: Thu Mar 20, 2003 8:14 pm
by Derk
Made both changes, got accepted. Thanks a ton. But, can you explain why this happened? I mean, in the other problems I've solved I use fgets/gets almost exclusively. Sometimes I use scanf, when it's unnecessary to have a character buffer at all.
I should have known DFS... I just took a class on AI hehe.
Thanks once again!
You were right!!
Posted: Sat Jun 07, 2003 6:34 pm
by Carlos
Hi!
I'm one of the judge administrators...I've checked problem #352 and you were right! There was an extra empty line at the end of the input! That's not an impossible test case, and it's not there on purpose.
Whenever you notice something like that, please mail us to
problemset@acm.uva.es! I can't read the whole topics in here...
I've changed the input, and I'm rejudging all submissions...
Sorry about the mistake.
Carlos.
Posted: Fri Oct 17, 2003 11:35 am
by Shaka_RDR
is it correct ?? i'm still confused .... any body have another sample input ? i've tried sample input at this thread before, and its exactly the same, but it's still WA... help
Code: Select all
#include <stdio.h>
#include <string.h>
int jml,idx;
char d1[30][30];
int b,k;
int eagle;
int no=0;
void main()
{
#ifndef ONLINE_JUDGE
freopen ("352.in","r",stdin);
freopen ("352.out","w",stdout);
#endif
while (scanf ("%d ",&jml)!=EOF)
{
no++;
eagle=0;
for (idx=0;idx<jml;idx++)
{
scanf ("%s ",&d1[idx]);
}
for (b=0;b<jml;b++)
{
for (k=0;k<jml;k++)
{
if (d1[b][k]=='1')
{
d1[b][k]='2';
if ((b-1)>=0 && (k-1) >=0 && d1[b-1][k-1]=='2')
{
}
else if ((b-1)>=0 && d1[b-1][k]=='2')
{
}
else if ((b-1)>=0 && (k+1)<jml && d1[b-1][k+1]=='2')
{
}
else if ((k-1)>=0 && d1[b][k-1]=='2')
{
}
else if ((k+1)<jml && d1[b][k+1]=='2')
{
}
else if ((b+1)<jml && (k-1)>=0 && d1[b+1][k-1]=='2')
{
}
else if ((b+1)<jml && d1[b+1][k]=='2')
{
}
else if ((b+1)<jml && (k+1)<jml && d1[b+1][k+1]=='2')
{
}
else
{
eagle++;
}
if ((b-1)>=0 && (k-1) >=0 && d1[b-1][k-1]=='1')
{
d1[b-1][k-1]='2';
}
else if ((b-1)>=0 && d1[b-1][k]=='1')
{
d1[b-1][k]='2';
}
else if ((b-1)>=0 && (k+1)<jml && d1[b-1][k+1]=='1')
{
d1[b-1][k+1]='2';
}
else if ((k-1)>=0 && d1[b][k-1]=='1')
{
d1[b][k-1]='2';
}
else if ((k+1)<jml && d1[b][k+1]=='1')
{
d1[b][k+1]='2';
}
else if ((b+1)<jml && (k-1)>=0 && d1[b+1][k-1]=='1')
{
d1[b+1][k-1]='2';
}
else if ((b+1)<jml && d1[b+1][k]=='1')
{
d1[b+1][k]='2';
}
else if ((b+1)<jml && (k+1)<jml && d1[b+1][k+1]=='1')
{
d1[b+1][k+1]='2';
}
}
}
}
printf ("Image number %d contains %d war eagles.\n",no,eagle);
}
}
[/code]
Posted: Mon Oct 20, 2003 2:04 am
by Shaka_RDR
sorry, my algorithm was wrong... i should've used recursive to solve this problem (but i didn't, cause i want to prove that i can solve this problem using iteration not recursive)...
to any body who still have WA , i suggest you to check with this sample input :
INPUT :
5
00000
01010
01010
01110
00000
OUTPUT :
Image number 1 contains 1 war eagles.
my code worked well except for this kind of input, but i've already got an AC for this problem ^_^ V (and also for 572 , its all the same)
352 - The Seasonal War
Posted: Sat Jan 10, 2004 10:59 am
by duaxorms
For some reason, my 352 keeps getting WA. I've thrown every piece of test input I can think at it. Tested boundary conditions, etc.
I don't know what is wrong......
here my code
[cpp]
#include <iostream.h>
#include <stdio.h>
int anal(int len);
void con(int i, int j);
int image[28][28];
int main()
{
int testnum=0;
int len;
while(scanf("%d", &len) != EOF)
{
int i, j, temp;
testnum++;
for(i=0; i<=28; i++)
for(int j=0; j<=28; j++)
image[j] = 0;
for(i=1; i<=len; i++)
{
scanf("%d", &temp);
for(j=len; j>=1; j--)
{
image[j] = temp % 10;
temp = temp / 10;
}
}
cout << "Image number " << testnum << " contains " << anal(len) << " war eagles." << endl;
}
return 0;
}
int anal(int len)
{
int i, j, count=0;
for(i=1; i<=len; i++)
for(j=1; j<=len; j++)
{
if(image[j]==1)
{
con(i, j);
count++;
}
}
return count;
}
void con(int i, int j)
{
image[j] = 0;
if(image[i-1][j-1] == 1)
con(i-1, j-1);
if(image[i-1][j] == 1)
con(i-1, j);
if(image[i-1][j+1] == 1)
con(i-1, j+1);
if(image[j-1] == 1)
con(i, j-1);
if(image[j+1] == 1)
con(i, j+1);
if(image[i+1][j-1] == 1)
con(i+1, j-1);
if(image[i+1][j] == 1)
con(i+1, j);
if(image[i+1][j+1] == 1)
con(i+1, j+1);
}
[/cpp][/cpp]