871 - Counting Cells in a Blob

Moderator: Board moderators

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

871 - Counting Cells in a Blob

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

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

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

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

Re: 871 - Counting Cells in a Blob

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

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

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

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

Re: 871 - Counting Cells in a Blob

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

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

Re: 871 - Counting Cells in a Blob

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

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!

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

Re: 871 - Counting Cells in a Blob

Check input and AC output for over 7,500 problems on uDebug!

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

Re: 871 - Counting Cells in a Blob

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