### 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

2 2

.A

A.

Could Somebody post more I/O's?

Wojciech

Page **1** of **3**

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

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

Note to self: Read more carefully next time.The first line will contain two numbers x and y, followed by x lines of y characters each.

Posted: **Tue Oct 25, 2005 1:10 am**

Guess why this fails.

Hint - it's correct on some compilers but wrong on the others...

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[64][64];
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

Appreciate

Posted: **Tue Oct 25, 2005 4:26 am**

Post your code. It's much easier to find critical inputs when you see the code.lonelyone wrote:I failed as well, could someone post more IO tests.

Appreciate

Posted: **Tue Oct 25, 2005 8:12 am**

cin >> data* ?!*

What exactly does that do? Is it as unsafe as gets( 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

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...

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**

You read input incorrectly:

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 ?

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 ?

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:
Thanks for any reply...

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 )
{
if ( head->next == NULL && head->alpha < alpha )
head->next = node;
else if ( head->next == NULL && head->alpha > alpha )
{
node->down = head->down;
node->next = head;
head->down = NULL;
head = node;
}
else if ( head->alpha > alpha )
{
node->next = head;
node->down = head->down;
head = node;
}
else
{
for ( col = head;
col->next->alpha < alpha && col->next != NULL;
col = col->next );
node->next = col->next;
col->next = node;
}
}
else
{
node->down = head;
head = node;
}
}
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
{
for ( curr = head;
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 )
{
curr = head;
while ( head != NULL )
{
head = head->down;
col = curr;
while ( curr != NULL )
{
printf( "%c %d\n", curr->alpha, curr->value );
curr = curr->next;
free( col );
col = curr;
}
curr = head;
}
}
}
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.

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!

Code: Select all

```
void floodFill( cint i, cint j )
{
return;
}
```

Hope this helps!

Posted: **Fri Nov 11, 2005 5:28 am**

Thanks for the reply...

But the new question is.. how to make floodFill function iteratively?

I'm not quite good in converting such recursive function into iterative function...

Any other idea...

But the new question is.. how to make floodFill function iteratively?

I'm not quite good in converting such recursive function into iterative function...

Any other idea...

Posted: **Sat Nov 12, 2005 8:06 pm**

We can convert recursive floodfill into iterative by using BFSRoby wrote:But the new question is.. how to make floodFill function iteratively?