Page 1 of 3

### 10946 - You want what filled?

Posted: Sat Oct 22, 2005 8:08 pm
What is the correct output for:
2 2
.A
A.

Could Somebody post more I/O's?

Wojciech

Posted: Sat Oct 22, 2005 8:27 pm

Code: Select all

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

Posted: Sat Oct 22, 2005 9:49 pm
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.

Posted: Tue Oct 25, 2005 1:10 am
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;
}
``````

Posted: Tue Oct 25, 2005 3:52 am
I failed as well, could someone post more IO tests.
Appreciate

Posted: Tue Oct 25, 2005 4:26 am
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.

Posted: Tue Oct 25, 2005 8:12 am
cin >> data ?!
What exactly does that do? Is it as unsafe as gets( data )?

Posted: Tue Oct 25, 2005 3:13 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

Posted: Wed Oct 26, 2005 10:07 am
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
``````

Posted: Wed Oct 26, 2005 10:33 am
The first line will contain two numbers x and y, followed by x lines of y characters each.

Posted: Wed Oct 26, 2005 1:02 pm
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 ?

### 10946 - You want what filled?

Posted: Mon Nov 07, 2005 7:52 pm
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;
}``````

Posted: Mon Nov 07, 2005 10:23 pm
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!

Posted: Fri Nov 11, 2005 5:28 am
Any other idea... We can convert recursive floodfill into iterative by using BFS 