871 - Counting Cells in a Blob

[1559]

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]

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]

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]

It looks like you figured it out.

[Alim14]

I am getting WA for missing 8 direction. Now AC

[moudud99]

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: 

[brianfry713]

Always print a newline char at the end of the last line.

[gautamzero]

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

Code: Select all

erased

[brianfry713]

Input:

Code: Select all

2

11000
01100
00101
10001
01011 

11000
01100
00101
10001
01011 

AC output:

Code: Select all

5

5

[gautamzero]

tnx brianfry
my code works for your I/O...but still WA

[brianfry713]

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

[uDebug]

Replying to follow the thread.

[m7moud.hussein]

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