10946 - You want what filled?
Moderator: Board moderators
10946 - You want what filled?
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
Guess why this fails. ![:)](./images/smilies/icon_smile.gif)
Hint - it's correct on some compilers but wrong on the others...
![:)](./images/smilies/icon_smile.gif)
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;
}
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...
![:-?](./images/smilies/icon_confused.gif)
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.
-
- 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:
Thanks for any reply...
This time for this problem I've got Runtime Error...
![:cry:](./images/smilies/icon_cry.gif)
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;
}
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!