871 - Counting Cells in a Blob

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

871 - Counting Cells in a Blob

Can somebody give me some tests for this problem I'm getting this problem WA can't understand why.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
It's not much, but...

Input:

Code: Select all

``````3

0000000000
0000000000
0000000000
0000000000
0000000000

1

11010
01100
00101
10001
01011``````
Output:

Code: Select all

``````0

1

6``````

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Thanks Per got AC.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
To those who are interested in this problem:

Don't let the low acceptance rate deceive you! I wrote my code without a compiler (I was using a public computer), so I contributed 2 Compile Errors and 1 Wrong Answer and led the statistics down... This problem is really not hard.

P.S. My WA is caused by missing 4 of the 8 possible directions (that means, my code cannot even handle the sample input correctly)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

871 - Counting Cells in a Blob

Code: Select all

``````
#include <stdio.h>
#include <string.h>

#define  MAXN  25

typedef enum {WHITE = 0, BLACK = 1} color;

int m; /* rows */
int n; /* cols */

color cell[MAXN][MAXN];

int visited[MAXN][MAXN];

void init()
{
int i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
visited[i][j] = 0;
}
}
}

int inLimit(int i, int j)
{
return ( (i >= 0) && (i < m) && (j >= 0) && (j < n) );
}

int dfs(int i, int j)
{
if (inLimit(i, j)) {
if ( (cell[i][j] == WHITE) || (visited[i][j]) ) {
return 0;
}
visited[i][j] = 1;
return  1 + dfs(i - 1, j - 1) + dfs(i - 1, j)     +
dfs(i - 1, j + 1) + dfs(i, j - 1)     +
dfs(i, j + 1)     + dfs(i + 1, j - 1) +
dfs(i + 1, j)     + dfs(i + 1, j + 1);
}
return 0;
}

int solve()
{
int i, j, spot_size;
int max = 0;

for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
if ((cell[i][j] == BLACK) && (!visited[i][j]) ) {
spot_size = dfs(i, j);
if (max < spot_size) {
max = spot_size;
}
}
}
}
return max;
}

int main()
{
int case_num;
int max_spot;
int len;
int i;
char line[MAXN + 1];

scanf("%d", &case_num);

while (case_num--) {
i = 0;
init();
while (1) {
scanf("%s", line);
len = strlen(line);
if ( (line[0] != '0') && (line[0] != '1') ) {
/* blank line, end of current case input */
m = i;
max_spot = solve();
printf("%d\n\n", max_spot);
break;
}
n = len;
while (len--) {
cell[i][len] = (color)(line[len] - '0');
}
i++;
}
}
return 0;
}

``````

I don't know what's the problem
please try to help me here!!!

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

871 - Counting Cells in a Blob

Code: Select all

``````CUT AFTER AC
``````
i can't find what's wrong..
Last edited by helloneo on Fri Jun 08, 2007 6:30 am, edited 3 times in total.

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Your programs give wrong result if I test with this input:

Code: Select all

``````5

11000
01100
00101
10001
01011

10101010
01010101
10101010
01010101
10101010
01010101
10101010
01010101

010101
101010
010101
101010
010101
101010

000000
000000
000000
000000
000000
000000

11111
11111
11111
11111
11111
``````
The result should be:

Code: Select all

``````5

32

18

0

25
``````
Yours:

Code: Select all

``````5

29

15

0

25
``````
Hope it helps

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Thanks.. I got AC..~
It was really stupid mistake.. ^^;

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Code: Select all

``````AC...ed
``````
Thx...

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

get wa

i get wa in 0.000.
can aney body help me?

Code: Select all

``````#include <iostream>
#include <string>

using namespace std;

int mx;
int ptr;
string s[26];
bool visited[26][26];
int len;

int isin(int i, int j)
{
if(i >= 0 && j >= 0 && i < ptr && j < len)
return 1;
return 0;
}

int dfs(int i, int j)
{
if(!isin(i, j) || visited[i][j] || s[i][j] == '0')
return 0;

visited[i][j] = 1;
return 1 + dfs(i + 1, j) + dfs(i , j + 1) + dfs(i - 1, j) + dfs(i, j - 1)
+ dfs(i + 1, j + 1) + dfs(i + 1, j - 1) + dfs(i - 1, j + 1) + dfs(i - 1, j - 1);
}

int main()
{
int n;
string s2;
cin >> n;
cin.ignore();
for(int N = 0;N < n;N++)
{
getline(cin, s2);
mx = 0;
ptr = 0;
while(getline(cin, s[ptr]), s[ptr] != "")
ptr++;
len  = s[0].size();
for(int i = 0;i < ptr;i++)
for(int j = 0;j < len;j++)
visited[i][j] = 0;
for(int i = 0;i < ptr;i++)
for(int j = 0;j < len;j++)
if(s[i][j] == '1' && !visited[i][j] )
{
int a = dfs(i, j);
if(mx < a)
mx = a;
}
cout << mx << endl;
if(N < n-1)
cout << endl;
}

return 0;
}
``````
thanks

rezaeeEE
New poster
Posts: 25
Joined: Fri May 11, 2007 3:45 pm

help

i get wa in 0.000.

Code: Select all

``````#include <iostream>
#include <string>

using namespace std;

int mx;
int ptr;
string s[26];
bool visited[26][26];
int len;

int isin(int i, int j)
{
if(i >= 0 && j >= 0 && i < ptr && j < len)
return 1;
return 0;
}

int dfs(int i, int j)
{
if(!isin(i, j) || visited[i][j] || s[i][j] == '0')
return 0;

visited[i][j] = 1;
return 1 + dfs(i + 1, j) + dfs(i , j + 1) + dfs(i - 1, j) + dfs(i, j - 1)
+ dfs(i + 1, j + 1) + dfs(i + 1, j - 1) + dfs(i - 1, j + 1) + dfs(i - 1, j - 1);
}

int main()
{
int n;
string s2;
cin >> n;
cin.ignore();
for(int N = 0;N < n;N++)
{
getline(cin, s2);
mx = 0;
ptr = 0;
while(getline(cin, s[ptr]), s[ptr] != "")
ptr++;
len  = s[0].size();
for(int i = 0;i < ptr;i++)
for(int j = 0;j < len;j++)
visited[i][j] = 0;
for(int i = 0;i < ptr;i++)
for(int j = 0;j < len;j++)
if(s[i][j] == '1' && !visited[i][j] )
{
int a = dfs(i, j);
if(mx < a)
mx = a;
}
cout << mx << endl;
if(N < n-1)
cout << endl;
}

return 0;
}
``````
thanks

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
You don't even get the correct answer for the test case in this thread..

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

871 - Counting Cells in a Blob

what's the reason of wrong answer?

Code: Select all

``````#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

#define SIZE 101

bool visited[SIZE][SIZE];
int v;

char in[100][101];
int cnt;

void visit(int u,int v)
{
int i;
visited[u][v]=true;
{
cnt++;
}
}

int DFS(int d,int d1)
{
int i,ncomp=0;
int k;
int max;
max = 0;
for(i=0;i< d;i++)
for( k = 0; k < d1; k++)
{
if(!visited[i][k] && in[i][k] == '1')
{
ncomp++;
cnt = 1;
visit(i,k);
if(cnt > max)
max = cnt;
}
}

return max;
}

int main(void)
{

int d,d1,i,j,i1;

int image = 1;
int t;

cin >> t;

getchar();
getchar();

i1 = 0;

while(t--)
{

while(1)
{
gets(in[i1]);

d = strlen(in[i1]);

if( d == 0)
{

int len = strlen(in[0]);
//cout << len << endl;
for(i = 0; i < i1; i++)
{
for( j = 0; j < len; j++)
{
if( in[i][j] == '1')
{

if( i-1>= 0)
{
if(in[i-1][j] == '1')
{
}

}
if( i-1>= 0 && j-1 >= 0)
{
if(in[i-1][j-1] == '1')
{
}

}
if(  j-1 >= 0)
{
if(in[i][j-1] == '1')
{
}

}
if(  j+1 < len)
{
if(in[i][j+1] == '1')
{
}

}
if( i+1 < i1 && j+1 < len)
{
if(in[i+1][j+1] == '1')
{
}

}
if( i+1 < i1)
{
if(in[i+1][j] == '1')
{
}

}
if( i-1 >= 0 && j+1 < len)
{
if(in[i-1][j+1] == '1')
{
}

}
if( i+1 < i1 && j-1 >= 0)
{
if(in[i+1][j-1] == '1')
{
}

}
}
}
}

//cout << i1 << endl;

int a = DFS(i1,strlen(in[0]));

if(image == 1)
image = 0;
else
cout << endl;

cout  << a << endl;

memset(visited,false,sizeof(visited));

i1 = 0;
//if(t > 0)
//getchar();
break;

}
else
{
i1++;
}

}

}

return 0;
}
``````

BUET
New poster
Posts: 22
Joined: Sun Jun 13, 2010 8:38 am

Re: 871 - Counting Cells in a Blob

I have found my fault. Input should be like square. So by calculating length of the first string , we can know how many rows will be followed. Then these two line have to use.
if(t > 0)
getchar();

joso
New poster
Posts: 1
Joined: Tue Apr 05, 2011 2:32 pm

Re: 871 - Counting Cells in a Blob

Hi,
I have a problem with my code. For each entry which I tested I got the right result. But I still have WA. I don't know if the bug is in the algorithm or somewhere in the output (incorrect format, ...).
``````Accepted!