Page 1 of 3

10946 - You want what filled?

Posted: Sat Oct 22, 2005 8:08 pm
by w k
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
by Larry

Code: Select all

Problem 1:
A 1
A 1

Posted: Sat Oct 22, 2005 9:49 pm
by Bj
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
by minskcity
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[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
by lonelyone
I failed as well, could someone post more IO tests.
Appreciate

Posted: Tue Oct 25, 2005 4:26 am
by minskcity
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
by Abednego
cin >> data ?!
What exactly does that do? Is it as unsafe as gets( data )?

Posted: Tue Oct 25, 2005 3:13 pm
by Tamagodzi
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
by pipo
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
by Cho
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
by pipo
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
by Roby
Hello everyone, I've a problem again...
This time for this problem I've got Runtime Error... :cry:
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;
}
Thanks for any reply...

Posted: Mon Nov 07, 2005 10:23 pm
by Bj
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
by Roby
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... :oops:

Posted: Sat Nov 12, 2005 8:06 pm
by angga888
Roby wrote:But the new question is.. how to make floodFill function iteratively?
We can convert recursive floodfill into iterative by using BFS :D