352 - The Seasonal War

[Betovsky]

hmm in this prob
this case
101
010
101

are 5 planes or only 1 plane?

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

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

[Betovsky]

Gracias , my head was starting to disintegrates...

i was starting to think of throwing my self over a bridge.

[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]

[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

[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]

[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);
                                        }

[Adrian Kuegel]

Use scanf instead of gets, then you will get Accepted.

[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

[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!

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

[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]

[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)

[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]