Page 2 of 2
871 - Counting Cells in a Blob
Posted: Fri Aug 19, 2011 7:37 pm
by 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
Re: 871 - Counting Cells in a Blob
Posted: Sun Aug 28, 2011 6:26 am
by 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
Re: 871 - Counting Cells in a Blob
Posted: Sun May 20, 2012 11:28 am
by 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;
}
Re: 871 - Counting Cells in a Blob
Posted: Sun May 20, 2012 8:46 pm
by brianfry713
It looks like you figured it out.
Re: 871 - Counting Cells in a Blob
Posted: Mon Feb 03, 2014 5:01 pm
by Alim14
I am getting WA for missing 8 direction. Now AC
Re: 871 - Counting Cells in a Blob
Posted: Tue Sep 30, 2014 11:09 am
by 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:
Re: 871 - Counting Cells in a Blob
Posted: Tue Sep 30, 2014 3:49 pm
by brianfry713
Always print a newline char at the end of the last line.
Re: 871 - Counting Cells in a Blob
Posted: Sat Jan 17, 2015 9:47 pm
by gautamzero
i'm getting WA
is there any critical i/o??
i tested all given i/o in this thread..
Re: 871 - Counting Cells in a Blob
Posted: Mon Jan 19, 2015 10:04 pm
by brianfry713
Input:
Code: Select all
2
11000
01100
00101
10001
01011
11000
01100
00101
10001
01011
AC output:
Re: 871 - Counting Cells in a Blob
Posted: Tue Jan 20, 2015 9:15 am
by gautamzero
tnx brianfry
my code works for your I/O...but still WA
Re: 871 - Counting Cells in a Blob
Posted: Wed Jan 21, 2015 5:57 am
by 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:
Re: 871 - Counting Cells in a Blob
Posted: Mon Apr 06, 2015 7:56 pm
by uDebug
Replying to follow the thread.
Re: 871 - Counting Cells in a Blob
Posted: Wed Oct 07, 2015 1:04 am
by 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;
}