10946 - You want what filled?

[w k]

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

Could Somebody post more I/O's?

Wojciech

[Larry]

Code: Select all

Problem 1:
A 1
A 1

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

[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;
}


[lonelyone]

I failed as well, could someone post more IO tests.
Appreciate

[minskcity]

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]

cin >> data[i] ?!
What exactly does that do? Is it as unsafe as gets( data[i] )?

[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

[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


[Cho]

You read input incorrectly:

The first line will contain two numbers x and y, followed by x lines of y characters each.

[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 ?

[Roby]

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

[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!

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

[angga888]

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

We can convert recursive floodfill into iterative by using BFS