871 - Counting Cells in a Blob

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

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

Post by Eduard » Wed Sep 15, 2004 2:58 pm

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

Post by Per » Wed Sep 15, 2004 3:18 pm

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

Post by Eduard » Wed Sep 15, 2004 6:02 pm

Thanks Per got AC. :D
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

Post by Observer » Wed Sep 15, 2004 6:15 pm

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) :oops:
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

Post by Yaron Wittenstein » Wed Jul 27, 2005 3:24 pm

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

Post by helloneo » Fri Nov 18, 2005 2:30 pm

Code: Select all

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

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » Tue Nov 29, 2005 8:49 am

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 :wink:

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

Post by helloneo » Wed Nov 30, 2005 7:53 pm

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:

871 : RE... Please Help !!!!

Post by jan_holmes » Fri Sep 01, 2006 7:16 pm

I got RE all the time, please help...

Code: Select all

AC...ed                
Thx...

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

get wa

Post by rezaeeEE » Mon Jul 23, 2007 2:11 pm

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

Post by rezaeeEE » Mon Jul 23, 2007 9:31 pm

i get wa in 0.000.
please help.

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

Post by helloneo » Tue Jul 24, 2007 4:57 am

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

Post by BUET » Fri Jan 07, 2011 3:10 pm

what's the reason of wrong answer?

Code: Select all

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

using namespace std;

#define SIZE 101

vector <int> adj[SIZE][SIZE];
vector <int> adj1[SIZE][SIZE];

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

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

void visit(int u,int v)
{
	int i;
	visited[u][v]=true;
	for(i=0;i<adj[u][v].size();i++)
	if(!visited[adj[u][v][i]][adj1[u][v][i]] && in[adj[u][v][i]][adj1[u][v][i]] == '1')
	{
		 cnt++;
	     visit(adj[u][v][i],adj1[u][v][i]);
	}
}

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')
								{
									adj[i][j].push_back(i-1);
									adj1[i][j].push_back(j);
								}
								
							}
							if( i-1>= 0 && j-1 >= 0)
							{
								if(in[i-1][j-1] == '1')
								{
									adj[i][j].push_back(i-1);
									adj1[i][j].push_back(j-1);
								}
								
							}
							if(  j-1 >= 0)
							{
								if(in[i][j-1] == '1')
								{
									adj[i][j].push_back(i);
									adj1[i][j].push_back(j-1);
								}
								
							}
							if(  j+1 < len)
							{
								if(in[i][j+1] == '1')
								{
									adj[i][j].push_back(i);
									adj1[i][j].push_back(j+1);
								}
								
							}
							if( i+1 < i1 && j+1 < len)
							{
								if(in[i+1][j+1] == '1')
								{
									adj[i][j].push_back(i+1);
									adj1[i][j].push_back(j+1);
								}
								
							}
							if( i+1 < i1)
							{
								if(in[i+1][j] == '1')
								{
									adj[i][j].push_back(i+1);
									adj1[i][j].push_back(j);
								}
								
							}
							if( i-1 >= 0 && j+1 < len)
							{
								if(in[i-1][j+1] == '1')
								{
									adj[i][j].push_back(i-1);
									adj1[i][j].push_back(j+1);
								}
								
							}
							if( i+1 < i1 && j-1 >= 0)
							{
								if(in[i+1][j-1] == '1')
								{
									adj[i][j].push_back(i+1);
									adj1[i][j].push_back(j-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

Post by BUET » Sun Jan 09, 2011 11:21 am

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

Post by joso » Tue Apr 05, 2011 2:55 pm

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, ...).
Thank you for your help.

My code:

Code: Select all

Accepted!

Post Reply

Return to “Volume 8 (800-899)”