871 - Counting Cells in a Blob

Eduard · 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.

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

It's not much, but...

Input:

Output:

Code: Select all

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

Thanks Per got AC.

Observer · 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)

Yaron Wittenstein · 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 · 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..~

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

Your programs give wrong result if I test with this input:

Code: Select all

The result should be:

Code: Select all

Yours:

Code: Select all

Hope it helps

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

Thanks.. I got AC..~
It was really stupid mistake.. ^^;

jan_holmes · 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 · 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 · 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 · 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 · 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 · 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 · 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!

OJ Board