871 - Counting Cells in a Blob
Moderator: Board moderators
871 - Counting Cells in a Blob
Can somebody give me some tests for this problem I'm getting this problem WA can't understand why.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
It's not much, but...
Input:
Output:
Input:
Code: Select all
3
0000000000
0000000000
0000000000
0000000000
0000000000
1
11010
01100
00101
10001
01011
Code: Select all
0
1
6
Thanks Per got AC. ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
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)![:oops:](./images/smilies/icon_redface.gif)
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)
![:oops:](./images/smilies/icon_redface.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
-
- New poster
- Posts: 18
- Joined: Wed Jul 21, 2004 5:09 pm
- Contact:
871 - Counting Cells in a Blob
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!!!
871 - Counting Cells in a Blob
Code: Select all
CUT AFTER AC
any advice plz..~
Last edited by helloneo on Fri Jun 08, 2007 6:30 am, edited 3 times in total.
-
- Experienced poster
- Posts: 101
- Joined: Wed May 04, 2005 4:33 pm
- Location: Tangerang, Banten, Indonesia
- Contact:
Your programs give wrong result if I test with this input:
The result should be:
Yours:
Hope it helps ![:wink:](./images/smilies/icon_wink.gif)
Code: Select all
5
11000
01100
00101
10001
01011
10101010
01010101
10101010
01010101
10101010
01010101
10101010
01010101
010101
101010
010101
101010
010101
101010
000000
000000
000000
000000
000000
000000
11111
11111
11111
11111
11111
Code: Select all
5
32
18
0
25
Code: Select all
5
29
15
0
25
![:wink:](./images/smilies/icon_wink.gif)
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
871 : RE... Please Help !!!!
I got RE all the time, please help...
Thx...
Code: Select all
AC...ed
get wa
i get wa in 0.000.
can aney body help me?
thanks
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;
}
help
i get wa in 0.000.
please help.
thanks
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;
}
871 - Counting Cells in a Blob
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;
}
Re: 871 - Counting Cells in a Blob
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();
if(t > 0)
getchar();
Re: 871 - Counting Cells in a Blob
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:
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!