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

1559
New poster
Posts: 2
Joined: Fri Aug 19, 2011 4:51 pm

871 - Counting Cells in a Blob

Post by 1559 » Fri Aug 19, 2011 7:37 pm

Code: Select all

#include<cstdio>
#include<cstring>
char s[100][100];
int n,c;
bool isvalid(int i,int j)
{
	return i>=0 && i<n && j>=0 && j<n;
}

int dx[]={0,0,1,-1,1,-1,-1,1};
int dy[]={1,-1,0,0,1,-1,1,-1};


void floodfill(int i,int j)
{int k;
	if(!isvalid(i,j))
		return ;
	
	else if(s[i][j]=='0')
		return ;
	else if(s[i][j]=='1')
	{s[i][j]='0';
		c++;
		for(k=0;k<8;k++)
		{
			floodfill(i+dx[k],j+dy[k]);}	}

}

int main()
{
	int i,j,k,m;
	int x,t;
	 char st[10];
	scanf("%d",&t);
	getchar();gets(st);
	for(x=1;x<=t;x++)
	{
		i=0;
		while(gets(st))
		{
			if(strcmp(st,"")==0)
				break;
			strcpy(s[i++],st);

		}
		n=i;

		m=0;
		for(i=0;i<n;i++)
		{
			for(j=0;j<n;j++)
			{
				if(s[i][j]=='1')
				{c=0;
					floodfill(i,j);
					if(c>m)
						m=c;
				}
			}
		}
		printf("%d\n",m);
		if(x!=t)
			puts("");

	}
	return 0;

}

I got RTE.....but can't find the reason

FelixP
New poster
Posts: 3
Joined: Sat Aug 20, 2011 5:48 pm

Re: 871 - Counting Cells in a Blob

Post by FelixP » Sun Aug 28, 2011 6:26 am

Code: Select all

bool isvalid(int i,int j)
{
   return i>=0 && i<n && j>=0 && j<n;
}
do you assume that row has the same number as col?
maybe this is the one that causes RTE

Parsa123
New poster
Posts: 1
Joined: Sun May 20, 2012 11:24 am

Re: 871 - Counting Cells in a Blob

Post by Parsa123 » Sun May 20, 2012 11:28 am

Pls help me i get WA

Code: Select all

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

char b[30][30];
string a;
int maxtmp;

void check(int i, int j)
{
	if (b[i][j] == '1')
	{
		b[i][j] = '2';
		for (int t = i - 1 ; t <= i + 1 ; t++)
			for (int k = j - 1 ; k <= j + 1 ; k++)
				if (b[t][k] == '1')
				{
					maxtmp++;
					check(t, k);
				}
	}
}

int main()
{
	int n, max;
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
	{
		memset(b, 0, sizeof b);
		max = maxtmp = 0;
		cin >> a;
		for (int j = 1 ; j <= a.size() ; j++)
			b[1][j] = a[j - 1];
		for (int j = 2 ; j <= a.size() ; j++)
			for (int k = 1 ; k <= a.size() ; k++)
				cin >> b[j][k];
		for (int j = 1 ; j <= a.size() ; j++)
		{
			for (int k = 1 ; k <= a.size() ; k++)
			{
				if (b[j][k] == '1')
				{
					maxtmp = 1;
					check(j, k);
				}
				if (maxtmp > max && maxtmp != 1)
					max = maxtmp;
			}
		}
		cout << max << "\n";
		if (i != n)
			cout << "\n";
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 871 - Counting Cells in a Blob

Post by brianfry713 » Sun May 20, 2012 8:46 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm
Location: BUBT,Dhaka, Bangladesh

Re: 871 - Counting Cells in a Blob

Post by Alim14 » Mon Feb 03, 2014 5:01 pm

I am getting WA for missing 8 direction. Now AC :)
When I believe it is possible, I always find a way

moudud99
New poster
Posts: 28
Joined: Fri Feb 08, 2013 1:40 pm

Re: 871 - Counting Cells in a Blob

Post by moudud99 » Tue Sep 30, 2014 11:09 am

can anyone find my mistake or give any output that my code fail?
my code is OK for all input of this thread.
Thanks in advance.

Code: Select all

Removed after AC.
thanks brainfry...... :wink: 
Last edited by moudud99 on Wed Oct 01, 2014 7:22 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 871 - Counting Cells in a Blob

Post by brianfry713 » Tue Sep 30, 2014 3:49 pm

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 871 - Counting Cells in a Blob

Post by gautamzero » Sat Jan 17, 2015 9:47 pm

i'm getting WA :(
is there any critical i/o??
i tested all given i/o in this thread..

Code: Select all

erased
Last edited by gautamzero on Wed Jan 21, 2015 11:50 am, edited 1 time in total.
None but a fool is always right..
so don't be upset when u r wrong..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 871 - Counting Cells in a Blob

Post by brianfry713 » Mon Jan 19, 2015 10:04 pm

Input:

Code: Select all

2

11000
01100
00101
10001
01011 

11000
01100
00101
10001
01011 
AC output:

Code: Select all

5

5
Check input and AC output for thousands of problems on uDebug!

gautamzero
New poster
Posts: 32
Joined: Fri Oct 10, 2014 1:10 pm
Location: Sylhet, Bangladesh

Re: 871 - Counting Cells in a Blob

Post by gautamzero » Tue Jan 20, 2015 9:15 am

tnx brianfry
my code works for your I/O...but still WA :(
None but a fool is always right..
so don't be upset when u r wrong..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 871 - Counting Cells in a Blob

Post by brianfry713 » Wed Jan 21, 2015 5:57 am

Input:

Code: Select all

2

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

1
AC output:

Code: Select all

0

1
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 871 - Counting Cells in a Blob

Post by uDebug » Mon Apr 06, 2015 7:56 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

m7moud.hussein
New poster
Posts: 1
Joined: Wed Oct 07, 2015 1:00 am

Re: 871 - Counting Cells in a Blob

Post by m7moud.hussein » Wed Oct 07, 2015 1:04 am

I get WA and i have tried udebug tesecases but still get WA help please

Code: Select all

#include <bits/stdc++.h>
using namespace std;
int TC, n;
char a[25], b;
short g[25][25];
bool visited[25][25];
short dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
short dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int ans, sum, m;
void debug() {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			cout << g[i][j];
		cout << endl;
	}
	cout << "----------" << sum << "-------" << endl;
}
void solve(int i, int j) {
	sum++;
	g[i][j] = 5;
	for (int k = 0; k < 8; k++) {
		int nx = i + dx[k], ny = j + dy[k];
		if (!visited[nx][ny] && g[nx][ny] && g[nx][ny] != -1 && nx >= 0
				&& ny >= 0) {
			visited[nx][ny] = true;
			solve(nx, ny);
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	bool nl = 0;
	cin >> TC;
	getchar();
	getchar();
	while (TC--) {
		ans = 0, sum = 0;
		memset(g, -1, sizeof(g));
		memset(visited, 0, sizeof(visited));
		m = 0;
		while (gets(a)) {
			if (a[0] == '\0')
				break;
			n = strlen(a);
			for (int i = 0; i < n; i++)
				a[i] == '1' ? g[m][i] = 1 : g[m][i] = 0;
			m++;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (!visited[i][j] && g[i][j]) {
					visited[i][j] = true;
					sum = 0;
					solve(i, j);
					ans = max(ans, sum);
				}
			}
		}
		if (nl)
			printf("\n");
		printf("%d\n", ans);
		nl = 1;
	}
	return 0;
}

Post Reply

Return to “Volume 8 (800-899)”