## 10946 - You want what filled?

Moderator: Board moderators

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

### 10946 - You want what filled?

What is the correct output for:
2 2
.A
A.

Could Somebody post more I/O's?

Wojciech

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Code: Select all

``````Problem 1:
A 1
A 1``````

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden
Edit: For crying out loud
The first line will contain two numbers x and y, followed by x lines of y characters each.
Note to self: Read more carefully next time.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Guess why this fails. Hint - it's correct on some compilers but wrong on the others...

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
using namespace std;

int n, m, test = 1;
char data;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int dfs(int y, int x, char c){
if(y < 0 || x < 0 || y >= n || x >= m || data[y][x] != c) return 0;
data[y][x] = '.';
int out = 1;
for(int d = 0; d < 4; d++) out += dfs(y + dy[d], x + dx[d], c);
return out;
}

int main(){

while(cin >> n >> m && n + m){
for(int i = 0; i < n; i++) cin >> data[i];
vector < pair < int, char > > ans;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(data[i][j] != '.') ans.push_back(make_pair(-dfs(i, j, ch), ch));
sort(ans.begin(), ans.end());
cout << "Problem " << test++ << ":" << endl;
for(int i = 0; i < (int)ans.size(); i++) cout << ans[i].second << " " << -ans[i].first << endl;
}

return 0;
}
``````

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
I failed as well, could someone post more IO tests.
Appreciate

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
lonelyone wrote:I failed as well, could someone post more IO tests.
Appreciate
Post your code. It's much easier to find critical inputs when you see the code.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
cin >> data ?!
What exactly does that do? Is it as unsafe as gets( data )?
If only I had as much free time as I did in college...

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm
It reads a string from input into the chararray with ending '\0'
i always use an array long enough and there were no bugs yet

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea
hi..

I am frustrated ...

in my view.. the algorithm is perfect..

but.. the judeger is "OUTPUT LIMITED EXCEEDED"

so terrible... where is wrong ?? anybody help me ??

the code is below...

Code: Select all

``````deleted after getting Acc
``````
Last edited by pipo on Tue Nov 01, 2005 3:56 am, edited 1 time in total.

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
The first line will contain two numbers x and y, followed by x lines of y characters each.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea
thank you.. Cho... You're right...

I skimmed through the problem After I changed "scanf("%d %d", &row, &col);" to "scanf("%d %d", &col, &row);", but.. now.. I got WA Could you give me some sample Inputs and Outputs ?

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

### 10946 - You want what filled?

Hello everyone, I've a problem again...
This time for this problem I've got Runtime Error... Can anyone help me to find where's the mistake...
Here's my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 55

typedef const int cint;
typedef struct data data;

char map[MAX][MAX];
int count, m, n;

struct data
{
int value;
char alpha;
data * next, * down;
} * head, * tail, * curr, * col;

void printData( void )
{
data * p, * q;
printf( "DATA:\n" );
for ( p = head; p != NULL; p = p->down, printf( "\n" ) )
for ( q = p; q != NULL; q = q->next )
printf( "%c %d, ", q->alpha, q->value );
}

void pushData( const int value, const char alpha )
{
data * node = ( data * ) malloc ( sizeof ( data ) );
node->value = value;
node->alpha = alpha;
node->next = NULL;
node->down = NULL;

if ( head == NULL )
head = curr = tail = col = node;
else if ( value >= head->value )
{
if ( value == head->value )
{
{
}
else if ( head->alpha > alpha )
{
}
else
{
col->next->alpha < alpha && col->next != NULL;
col = col->next );
node->next = col->next;
col->next = node;
}
}
else
{
}
}
else if ( value <= tail->value )
{
if ( value == tail->value )
{
if ( tail->next == NULL && tail->alpha < alpha )
tail->next = node;
else if ( tail->next == NULL && tail->alpha > alpha )
{
for ( col = head; col->down != tail; col = col->down );
node->next = tail;
col->down = node;
tail = node;
}
else if ( tail->alpha > alpha )
{
for ( col = head; col->down != tail; col = col->down );
node->next = tail;
col->down = node;
tail = node;
}
else
{
for ( col = tail;
col->next->alpha < alpha && col->next != NULL;
col = col->next );
node->next = col->next;
col->next = node;
}
}
else
{
tail->down = node;
tail = node;
}
}
else
{
curr->down->value > value && curr->down != NULL;
curr = curr->down );

if ( curr->down->value == value )
{
col = curr;
curr = curr->down;

if ( curr->next == NULL && curr->alpha < alpha )
curr->next = node;
else if ( curr->next == NULL && curr->alpha > alpha )
{
node->next = curr;
node->down = curr->down;
curr->down = NULL;
col->down = node;
}
else if ( curr->alpha > alpha )
{
node->next = curr;
node->down = curr->down;
curr->down = NULL;
col->down = node;
curr = node;
}
else
{
for ( col = curr;
col->next->alpha < alpha && col->next != NULL;
col = col->next );
node->next = col->next;
col->next = node;
}
}
else
{
node->down = curr->down;
curr->down = node;
}
}

// printData();
}

void popData( void )
{
if ( head != NULL )
{

while ( head != NULL )
{
col = curr;

while ( curr != NULL )
{
printf( "%c %d\n", curr->alpha, curr->value );

curr = curr->next;
free( col );
col = curr;
}

}
}
}

void floodFill( cint i, cint j )
{
char c = map[i][j];

map[i][j] = '.'; count++;

// east
if ( j + 1 < n && map[i][j + 1] == c )
floodFill( i, j + 1 );

// south
if ( i + 1 < m && map[i + 1][j] == c )
floodFill( i + 1, j );

// west
if ( j - 1 >= 0 && map[i][j - 1] == c )
floodFill( i, j - 1 );

// north
if ( i - 1 >= 0 && map[i - 1][j] == c )
floodFill( i - 1, j );
}

int main()
{
int a = 0, b = 0, ctr = 1;
char alpha = 0;

while ( scanf( "%d %d\n", &m, &n ) == 2 )
{
if ( !m && !n )
break;

head = curr = tail = NULL;

for ( a = 0; a < m; a++ )
{
memset( map[a], '\0', sizeof( map[a] ) );
gets( map[a] );
}

for ( a = 0; a < m; a++ )
for ( b = 0; b < n; b++ )
if ( map[a][b] != '.' )
{
count = 0; alpha = map[a][b];
floodFill( a, b );
pushData( count, alpha );
}

printf( "Problem %d:\n", ctr++ );
popData();
}

return 0;
}``````

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden
Your floodFill function is not very stack-friendly. Try to replace your floodFill with an empty function to see if you get wrong answer instead.

Code: Select all

``````void floodFill( cint i, cint j )
{
return;
}
``````
If you get WA, try to write an iterative flood fill. An ugly but easy way to do this is to directly convert your current function with a loop and implement a memory based stack data structure.

Hope this helps!

Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:
Any other idea... We can convert recursive floodfill into iterative by using BFS 