10946 - You want what filled?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

10946 - You want what filled?

Post by w k » 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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Oct 22, 2005 8:27 pm

Code: Select all

Problem 1:
A 1
A 1

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

Post by Bj » 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.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » 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[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
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Tue Oct 25, 2005 3:52 am

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

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » 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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Oct 25, 2005 8:12 am

cin >> data ?!
What exactly does that do? Is it as unsafe as gets( data )?
If only I had as much free time as I did in college...

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » 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

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » 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
Last edited by pipo on Tue Nov 01, 2005 3:56 am, edited 1 time in total.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » 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.

pipo
New poster
Posts: 47
Joined: Tue May 11, 2004 6:43 pm
Location: Republic of Korea

Post by pipo » 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 ?

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

10946 - You want what filled?

Post by Roby » Mon Nov 07, 2005 7:52 pm

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

Bj
New poster
Posts: 24
Joined: Mon Oct 17, 2005 1:39 am
Location: Sweden

Post by Bj » 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!

User avatar
Roby
Experienced poster
Posts: 101
Joined: Wed May 04, 2005 4:33 pm
Location: Tangerang, Banten, Indonesia
Contact:

Post by Roby » 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... :oops:

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat Nov 12, 2005 8:06 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”