10267 - Graphical Editor

[tellez12]

i read all the post about this problems and didint help me, my function for flood is iterative, i check if X>X2 and Y>Y2, tried the few input-output in the forum for this problem and still getting the WA and is driving me crazy, so if plz anyone can check out my code or post or send me some input output it will be really apreciated.
here is my code

Code: Select all

#include <stdio.h>


int i,j,m,n,y,x,x2,y2,other;
char c;
char c1;
char mat[260][260];
char nombre[100];
short marcado[260][260];
int visitados;
int encontrados;
int cords[67][2];

void ini(){
   
   for(i=1;i<=n;i++){
      for(j=1;j<=m;j++){
         mat[i][j]='O';
      }
   }

}
void colorear(unsigned char x,unsigned char y){

   if(mat[y][x]==c){
      mat[y][x]=c1;   
      visitados++;
      marcado[y][x]=1;

      if(x+1<=m && !marcado[y][x+1] && mat[y][x+1]==c){
         marcado[y][x+1]++;
         encontrados++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x+1;

      }
     
      if(x-1>0 && !marcado[y][x-1] && mat[y][x-1]==c){
         encontrados++;
         marcado[y][x-1]++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x-1;
         

      }
     
      if(y+1<=n && !marcado[y+1][x] && mat[y+1][x]==c){
         marcado[y+1][x]++;
         encontrados++;
         cords[encontrados][0]=y+1;
         cords[encontrados][1]=x;
         


      }
      if(y-1>0 && !marcado[y-1][x] && mat[y-1][x]==c){
         encontrados++;
         marcado[y-1][x]++;
         cords[encontrados][0]=y-1;
         cords[encontrados][1]=x;
         


      }

   }

}

void mayor(int &a,int &b){
int aux;
   if (a>b){
      aux=a;
      a=b;
      b=aux;
   }


}
int main(){
   other=0;
   scanf("%c",&c);
   while (1){

      if(c=='I'){
         scanf("%d %d",&m,&n);
         ini();
      }
      else if(c=='C'){
         ini();
      }
      else if(c=='L'){
         scanf("%d %d%c%c",&x,&y,&c,&c);
         mat[y][x]=c;
      }
      else if(c=='V'){
         scanf("%d %d %d%c%c",&x,&y,&y2,&c,&c);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            mat[i][x]=c;
      }
      else if(c=='H'){
         scanf("%d %d %d%c%c",&x,&x2,&y,&c,&c);
         mayor(x,x2);
         for (j=x;j<=x2;j++)
            mat[y][j]=c;
      }
      else if(c=='K'){
         scanf("%d %d %d %d%c%c",&x,&y,&x2,&y2,&c,&c);
         mayor(x,x2);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            for(j=x;j<=x2;j++)
            mat[i][j]=c;
      }
      else if (c=='F'){
         scanf("%d %d%c%c",&x,&y,&c1,&c1);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            marcado[i][j]=0;
            }
         }
         c=mat[y][x];
         visitados=0;
         encontrados=0;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x;
     
         while(visitados<=encontrados){
            colorear(cords[visitados][1],cords[visitados][0]);
           
           
         }   
         
         
      }
      else if (c=='S'){
         scanf("%s",nombre);
         printf("%s\n",nombre);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            printf("%c",mat[i][j]);
            }
            printf("\n");

         }


      }
      else if(c=='X')
         break;
      else
         other=1;

         
      if(other){
      gets(nombre);
      scanf("%c",&c);
      other=0;
      }
      else     
      scanf("%c %c",&c,&c);
     
   }





return 0;
}

my emails is luistellez@gmail.com if anyone can send me some info there or test cases or something it will be really apreciate it.[/code]

[tellez12]

I read all the post about this problems and didint help me, my function for flood is iterative, i check if X>X2 and Y>Y2, tried the few input-output in the forum for this problem and still getting the WA and is driving me crazy, so if plz anyone can check out my code or post or send me some input output it will be really apreciated.
here is my code.

Code: Select all

#include <stdio.h>


int i,j,m,n,y,x,x2,y2,other;
char c;
char c1;
char mat[260][260];
char nombre[100];
short marcado[260][260];
int visitados;
int encontrados;
int cords[67][2];

void ini(){
   
   for(i=1;i<=n;i++){
      for(j=1;j<=m;j++){
         mat[i][j]='O';
      }
   }

}
void colorear(unsigned char x,unsigned char y){

   if(mat[y][x]==c){
      mat[y][x]=c1;   
      visitados++;
      marcado[y][x]=1;

      if(x+1<=m && !marcado[y][x+1] && mat[y][x+1]==c){
         marcado[y][x+1]++;
         encontrados++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x+1;

      }
     
      if(x-1>0 && !marcado[y][x-1] && mat[y][x-1]==c){
         encontrados++;
         marcado[y][x-1]++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x-1;
         

      }
     
      if(y+1<=n && !marcado[y+1][x] && mat[y+1][x]==c){
         marcado[y+1][x]++;
         encontrados++;
         cords[encontrados][0]=y+1;
         cords[encontrados][1]=x;
         


      }
      if(y-1>0 && !marcado[y-1][x] && mat[y-1][x]==c){
         encontrados++;
         marcado[y-1][x]++;
         cords[encontrados][0]=y-1;
         cords[encontrados][1]=x;
         


      }

   }

}

void mayor(int &a,int &b){
int aux;
   if (a>b){
      aux=a;
      a=b;
      b=aux;
   }


}
int main(){
   other=0;
   scanf("%c",&c);
   while (1){

      if(c=='I'){
         scanf("%d %d",&m,&n);
         ini();
      }
      else if(c=='C'){
         ini();
      }
      else if(c=='L'){
         scanf("%d %d%c%c",&x,&y,&c,&c);
         mat[y][x]=c;
      }
      else if(c=='V'){
         scanf("%d %d %d%c%c",&x,&y,&y2,&c,&c);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            mat[i][x]=c;
      }
      else if(c=='H'){
         scanf("%d %d %d%c%c",&x,&x2,&y,&c,&c);
         mayor(x,x2);
         for (j=x;j<=x2;j++)
            mat[y][j]=c;
      }
      else if(c=='K'){
         scanf("%d %d %d %d%c%c",&x,&y,&x2,&y2,&c,&c);
         mayor(x,x2);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            for(j=x;j<=x2;j++)
            mat[i][j]=c;
      }
      else if (c=='F'){
         scanf("%d %d%c%c",&x,&y,&c1,&c1);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            marcado[i][j]=0;
            }
         }
         c=mat[y][x];
         visitados=0;
         encontrados=0;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x;
     
         while(visitados<=encontrados){
            colorear(cords[visitados][1],cords[visitados][0]);
           
           
         }   
         
         
      }
      else if (c=='S'){
         scanf("%s",nombre);
         printf("%s\n",nombre);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            printf("%c",mat[i][j]);
            }
            printf("\n");

         }


      }
      else if(c=='X')
         break;
      else
         other=1;

         
      if(other){
      gets(nombre);
      scanf("%c",&c);
      other=0;
      }
      else     
      scanf("%c %c",&c,&c);
     
   }





return 0;
}


my emails is luistellez@gmail.com if anyone can send me some info there or test cases or something it will be really apreciate it.

[tellez12]

I read all the post about this problems and didint help me, my function for flood is iterative, i check if X>X2 and Y>Y2, tried the few input-output in the forum for this problem and still getting the WA and is driving me crazy, so if plz anyone can check out my code or post or send me some input output it will be really apreciated.
here is my code.

Code: Select all

#include <stdio.h>


int i,j,m,n,y,x,x2,y2,other;
char c;
char c1;
char mat[260][260];
char nombre[100];
short marcado[260][260];
int visitados;
int encontrados;
int cords[67][2];

void ini(){
   
   for(i=1;i<=n;i++){
      for(j=1;j<=m;j++){
         mat[i][j]='O';
      }
   }

}
void colorear(unsigned char x,unsigned char y){

   if(mat[y][x]==c){
      mat[y][x]=c1;   
      visitados++;
      marcado[y][x]=1;

      if(x+1<=m && !marcado[y][x+1] && mat[y][x+1]==c){
         marcado[y][x+1]++;
         encontrados++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x+1;

      }
     
      if(x-1>0 && !marcado[y][x-1] && mat[y][x-1]==c){
         encontrados++;
         marcado[y][x-1]++;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x-1;
         

      }
     
      if(y+1<=n && !marcado[y+1][x] && mat[y+1][x]==c){
         marcado[y+1][x]++;
         encontrados++;
         cords[encontrados][0]=y+1;
         cords[encontrados][1]=x;
         


      }
      if(y-1>0 && !marcado[y-1][x] && mat[y-1][x]==c){
         encontrados++;
         marcado[y-1][x]++;
         cords[encontrados][0]=y-1;
         cords[encontrados][1]=x;
         


      }

   }

}

void mayor(int &a,int &b){
int aux;
   if (a>b){
      aux=a;
      a=b;
      b=aux;
   }


}
int main(){
   other=0;
   scanf("%c",&c);
   while (1){

      if(c=='I'){
         scanf("%d %d",&m,&n);
         ini();
      }
      else if(c=='C'){
         ini();
      }
      else if(c=='L'){
         scanf("%d %d%c%c",&x,&y,&c,&c);
         mat[y][x]=c;
      }
      else if(c=='V'){
         scanf("%d %d %d%c%c",&x,&y,&y2,&c,&c);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            mat[i][x]=c;
      }
      else if(c=='H'){
         scanf("%d %d %d%c%c",&x,&x2,&y,&c,&c);
         mayor(x,x2);
         for (j=x;j<=x2;j++)
            mat[y][j]=c;
      }
      else if(c=='K'){
         scanf("%d %d %d %d%c%c",&x,&y,&x2,&y2,&c,&c);
         mayor(x,x2);
         mayor(y,y2);
         for (i=y;i<=y2;i++)
            for(j=x;j<=x2;j++)
            mat[i][j]=c;
      }
      else if (c=='F'){
         scanf("%d %d%c%c",&x,&y,&c1,&c1);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            marcado[i][j]=0;
            }
         }
         c=mat[y][x];
         visitados=0;
         encontrados=0;
         cords[encontrados][0]=y;
         cords[encontrados][1]=x;
     
         while(visitados<=encontrados){
            colorear(cords[visitados][1],cords[visitados][0]);
           
           
         }   
         
         
      }
      else if (c=='S'){
         scanf("%s",nombre);
         printf("%s\n",nombre);
         for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
            printf("%c",mat[i][j]);
            }
            printf("\n");

         }


      }
      else if(c=='X')
         break;
      else
         other=1;

         
      if(other){
      gets(nombre);
      scanf("%c",&c);
      other=0;
      }
      else     
      scanf("%c %c",&c,&c);
     
   }





return 0;
}


my emails is luistellez@gmail.com if anyone can send me some info there or test cases or something it will be really apreciate it.

[JM]

IDK what compiler you're using, but that doesn't compile with gcc. You'd have to change the mayor function to take pointers, and pass it addresses. Also change the temp int to a pointer. Lastly, don't use gets. Use fgets. Other than that, looks pretty much fine.

[RalphLoizzo]

It's killing my stats.



I've tried everything I can think of with the flood fill. What happens to commands whose parameters run off the image table? Do they actually do anything? Or are we supposed to ignore those commands.

I'm not sure where to diagnose the wrong answer here.

Code: Select all

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

char matrix [251][251];
int fill (int x,int  y, int boundx, int boundy, char oldcolor, char newcolor)
{
   if ((x<1) or (y<1)) return 0;
   if ((x>boundx) or (y>boundy)) return 0;
   matrix[y][x]=newcolor;
   if (matrix[y][x-1] == oldcolor)
      fill (x-1, y, boundx, boundy, oldcolor, newcolor);
   if (matrix[y-1][x] == oldcolor)
      fill (x, y-1, boundx, boundy, oldcolor, newcolor);
   if (matrix[y+1][x] == oldcolor)
      fill (x, y+1, boundx, boundy, oldcolor, newcolor);
   if (matrix[y][x+1] == oldcolor)
      fill (x+1, y, boundx, boundy, oldcolor, newcolor);
}


int main ()
{
   string theinput;
   bool finished= false;
   int      boundaryx=250;
   int       boundaryy=250;
   while ( (finished != true) &&  getline (cin, theinput) )
   {
      istringstream thestream(theinput);
      string command;
      thestream  >> command;
      if (command == "F")
      {
         int x, y; char c;
         thestream >> x >> y >> c;
         char theprevcolor = matrix[y][x];
         if (c != theprevcolor)
            fill (x,y, boundaryx, boundaryy, theprevcolor, c);
         
 
      }

      if (command == "X")
      {
         finished = true;
      }
      if (command == "I")
      {
         int x, y;
         thestream >> x >> y;
         for (int Xcounter = 1; Xcounter < (x+1); Xcounter++)
         {
            for (int Ycounter = 1; Ycounter < (y+1); Ycounter++)
            {
               matrix [Ycounter][Xcounter] = 'O';
            }
         }
         boundaryx=x; boundaryy=y;

      }
      if (command == "S")
      {
         string filename;
         thestream >> filename;
         cout << filename << endl;
         for (int Ycounter=1; Ycounter < (boundaryy +1 ); Ycounter++)
         {
            for (int Xcounter = 1; Xcounter< (boundaryx+1); Xcounter++)
            {
               cout << matrix[Ycounter][Xcounter];
            }
            cout << endl;
         }
      }
      if (command == "L")
      {
         int x; int y; char c;
         thestream >> x >> y >> c;
         matrix[y][x]=c;
      }
      if (command == "C")
      {
         // clear the table
         for (int Xc = 1; Xc < (boundaryx+1); Xc ++)
         {
            for (int Yc=1; Yc < (boundaryy+1); Yc ++)
            {
               matrix[Yc][Xc]='O';
            }
         }
      }
      if (command == "V")
      {
         int x, y1, y2, temp;
         char c;
         
         thestream >> x >> y1 >> y2>> c;
         if (y1 > y2)
         {
            temp = y1;
            y1 = y2;
            y2 = temp;
         }

         for (int Yc=y1; Yc < (y2+1); Yc++)
         {
            matrix [Yc][x] = c;
         }
      }
      if (command == "H")
      {
         int x1, x2, y, temp;
         char c;
         thestream >> x1 >> x2 >> y >> c;
         if (x1 > x2)
         {
            temp = x1;
            x1 = x2;
            x2 = temp;
         }
         for (int Xc=x1; Xc < (x2+1); Xc++)
         {
            matrix[y][Xc] = c;
         }
      }
      if (command == "K")
      {
         int x1, y1, x2, y2;
         char c;
         thestream >> x1 >> y1 >> x2 >> y2;
         if (x2 > boundaryx)   break;
         if (y2 > boundaryy)  break;
         if (x1 < 1) break;
         if (y1 < 1) break;

         for (int Yc=y1; Yc < (y2+1); Yc++)
         {
            for (int Xc=x1; Xc < (x2+1); Xc++)
            {
               matrix[Yc][Xc]=c;
            }
         }
      }
   
   }
   return 0;
}


[RalphLoizzo]

this may help you....

We've been told time and time again to really examine the floodfill routine. And I did. I went over and over again with it, and still couldnt find the problem. I even entertained what does the C command really do? Does it clear the image only? Or the entire board....

I've submitted this dang problem over 20 times. I don't like things unfinished.

So I went through my code line by line, and finally I got ACCEPTED. Thanks to all of you who made suggestions on other posts on the board. But if you want to see the error I made - just look at this simple problem.

In my code to fill a rectangle (the K command) I noticed this problem with my C++ code.

Code: Select all

if (command == "K")
      {
         int x1, y1, x2, y2;
         char c;
         thestream >> x1 >> y1 >> x2 >> y2;
         if (x2 > boundaryx)   break;
         if (y2 > boundaryy)  break;
         if (x1 < 1) break;
         if (y1 < 1) break;

         for (int Yc=y1; Yc < (y2+1); Yc++)
         {
            for (int Xc=x1; Xc < (x2+1); Xc++)
            {
               matrix[Yc][Xc]=c;
            }

Seems correct right?

Well notice the line where I get the variables for the coordinates.
I never set the color variable 'c'. The line above should read:
thestream >> x1 >> y1 >> x2 >> y2 >> c;

I resubmitted my code - and sure enough I got the ACCEPTED.

So even though you may think ALL your code is correct, it helps to really look at it line by line, step by step, just to see what's wrong. I studied the floodfill routine and spent so much time on that, I neglected what should have been obvious.

This was a good lesson to learn.

[t_sergiu]

I have tried various test cases and am confident my code works. I have checked all commands and made sure to check for bounds, x1 being smaller than x2, etc.. any help would be appreciated.

EDIT: NVM, my code works, I was simply filling the empty array with 0 (zero), whereas empty is O (capital o)

[trokan]

consider the possibility that for case F, the color in (X,Y) is the same as new color, if this is true, your programs recurses too deeply causing a runtime error

[trokan]

it just doesnt recurse too deeply, it will never stop calling itselft over and over again, since the conditions that you have established will always be met.

[trokan]

I have gone through everything, iterative flood fill, recursive flood fill, check if X1>X2, Y1>Y2 and all we have discussed before, i keep getting wrong answer with the implementation shown below, if anybody finds a problem i would gladly appreciated.

Code: Select all

import java.io.*;
import java.util.*;

class Main
{
   static char mat[][]=new char[1][1];
   public static void main(String args[])throws IOException
   {
      BufferedReader lee = new BufferedReader(new InputStreamReader(System.in));
      String s;
      StringTokenizer str;
      while(!(s=lee.readLine()).equals("X"))
      {
         char K;
         char C;
         str=new StringTokenizer(s);
         C=str.nextToken().charAt(0);
         if(C=='I')
         {
            int p=Integer.parseInt(str.nextToken());
            mat=new char[Integer.parseInt(str.nextToken())][p];
            Fill();
         }
         else if(C=='C')Fill();
         else if(C=='L')
         {
            int X=Integer.parseInt(str.nextToken())-1;
            int Y=Integer.parseInt(str.nextToken())-1;
            mat[Y][X]=str.nextToken().charAt(0);
         }
         else if(C=='V')
         {
            int col=Integer.parseInt(str.nextToken())-1;
            int A=Integer.parseInt(str.nextToken())-1;
            int B=Integer.parseInt(str.nextToken())-1;
            if(A>B)
            {
               int aux=A;
               A=B;
               B=aux;
            }
            K=str.nextToken().charAt(0);
            for(int i=A;i<=B;i++)mat[i][col]=K;      
         }
         else if(C=='H')
         {
            int A=Integer.parseInt(str.nextToken())-1;
            int B=Integer.parseInt(str.nextToken())-1;
            int row=Integer.parseInt(str.nextToken())-1;
            if(A>B)
            {
               int aux=A;
               A=B;
               B=aux;
            }
            K=str.nextToken().charAt(0);
            for(int i=A;i<=B;i++)
               mat[row][i]=K;      
         }
         else if(C=='K')
         {
            int A=Integer.parseInt(str.nextToken())-1;
            int B=Integer.parseInt(str.nextToken())-1;
            int D=Integer.parseInt(str.nextToken())-1;
            int E=Integer.parseInt(str.nextToken())-1;
            K=str.nextToken().charAt(0);
            for(int i=B;i<=E;i++)
               for(int j=A;j<=D;j++)
                  mat[i][j]=K;
         }
         else if(C=='F')
         {
            int X=Integer.parseInt(str.nextToken())-1;
            int Y=Integer.parseInt(str.nextToken())-1;
            char colorear=mat[Y][X];
            K=str.nextToken().charAt(0);
            if(K==colorear)continue;
            Floooooood(X,Y,K,colorear);
         
         }
         else if(C=='S')
         {
            System.out.println(str.nextToken());
            for(int i=0;i<mat.length;i++)
            {
               for(int j=0;j<mat[0].length;j++) 
                  System.out.print(mat[i][j]);
               System.out.println();
            }      
         }
      }
   }
   public static void Floooooood(int X,int Y, char K, char colorear)
   {
      mat[Y][X]=K;
      if(X+1<mat[0].length&&mat[Y][X+1]==colorear)
      {
         Floooooood(X+1,Y,K,colorear);
      }
      if(Y+1<mat.length&&mat[Y+1][X]==colorear)
      {
         Floooooood(X,Y+1,K,colorear);
      }
      if(X-1>=0&&mat[Y][X-1]==colorear)
      {
         Floooooood(X-1,Y,K,colorear);
      }
      if(Y-1>=0&&mat[Y-1][X]==colorear)
      {
         Floooooood(X,Y-1,K,colorear);
      }
      
   }


   public static void Fill()
   {
      for(int i=0;i<mat.length;i++)
         for(int j=0;j<mat[0].length;j++)
            mat[i][j]='O';
   }
}

[x140l31]

Hi!

I have RE with this program, I think it must be my "fill region" function. I'm programming in Java and my "full region" function is a recursive function. With a "big" input:

Code: Select all

I 150 150
F 1 1 J


I have this error "Exception in thread "main" java.lang.StackOverflowError"

in Java there's a limit of recursive calls???

sorry about my bad English

[JINX]

I was really screwed up when i got WAs over and over, plz some help me. thanks.

Code: Select all

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int flood(char pc[][250],int x , int y , char color , char old_color,int m,int n);


int main()
{
   string s,name;
   int n;//row
   int m;//column
   char color,old_color;
   int x,y,x1,x2,y1,y2;

   char pc[250][250];

   while(1)
   {

   
      getline(cin,s);
      istringstream stream(s);
      char lead;
      stream>>lead;
      switch (lead)
      {
      case 'X':
         return 0;
      case 'I':
         stream>>m>>n;
         if (m>250||n>250||m<0||n<0)
            return 0;
         
         for (int i = 0 ; i<n ; i++)
         {
            
            for ( int j = 0 ; j< m ; j++)
            {
               pc[i][j] = 'O';
            }
            
         }
         break;
      case  'C':
         for (int i = 0 ;i<n;i++)
         {
            for (int j = 0 ; j<m ; j++)
            {
               pc[i][j] = 'O';
            }
         }
         break;
      case 'L':
         stream>>x>>y>>color;
         pc[y-1][x-1] = color;
         break;
      case 'V':
         stream>>x>>y1>>y2>>color;
         for (int i = y1-1 ; i<y2 ; i++)
         {
            pc[i][x-1] = color;
         }
         break;
      case 'H':
         stream>>x1>>x2>>y>>color;
         for (int i = x1-1 ;i<x2 ;i++)
         {
            pc[y-1][i] = color;
         }
         break;
      case 'K':
         stream>>x1>>y1>>x2>>y2>>color;
         for ( int i = y1-1; i<y2 ; i++)
         {
            for ( int j = x1-1; j<x2 ;j++)
               pc[i][j] = color;
         }
         break;
      case 'F':
         stream>>x>>y>>color;
         old_color = pc[y-1][x-1];
         //pc[y-1][x-1] = color;
         flood(pc,x,y,color,old_color,m,n);

         break;
      case 'S':
         stream>>name;
         cout<<name<<endl;
         for (int i = 0 ; i<n ;i++)
         {
            for (int j = 0 ; j<m ; j++)
            {
               cout<<pc[i][j];
            }
            cout<<endl;
         }
         break;
      default :
         ;
      }
   }//end while
   return 0;
}

int flood(char pc[][250],int x , int y , char color , char old_color,int m ,int n)
{
   
   if ( pc[y-1][x-1] == color )
      return 0;

   else if (pc[y-1][x-1] == old_color)
   {
      pc[y-1][x-1] = color;
      if (x+1<=m)
      flood(pc,x+1,y,color,old_color,m,n);
      if (x-1>=1)
      flood(pc,x-1,y,color,old_color,m,n);
      if (y+1<=n)
      flood(pc,x,y+1,color,old_color,m,n);
      if (y-1>=1)
      flood(pc,x,y-1,color,old_color,m,n);

   }
   return 0;
}




[rabiee]

Hi all,
My code takes forever(TLE) on getline statement in the judge, but works fine on my machine.
Can anyone help?

[JobAvatar]

Just tried and solved it in Java. This is a very interesting problem when you compare the C++/C solutions with the Java one. I'm not gonna elaborate the algorithm as for this problem it is simply *following the instructions*. But certain things can go wrong when you use Java here, and there is a ridiculous one in this problem: printing...

1. No matter which language you pick, make sure you reflect the meaning of the word 'between' for V, H cmd in the code and that M is the column number not the row's.

2. Use the Scanner class instead of the whatever methods you r trying to craft to read the input, this is Java 1.6, so we use everything that r made available to us already by the programming language.

*3. Forget about the recursive version of the flooding algorithm, use a Queue or just LinkedList to implement the filling op, it doesn't matter if you check the color before filling or not, you'll get stack overflow anyway which leads to a [Runtime Error](RE).
[test case:
I 250 250
F 1 1 T
]
make sure you don't get any exception thrown during the test.(This doesn't mean you need to handle them, just run and see if the program crashes on an exception.)

4. O not 0

*5. Print the picture 2-D char array in a 1-D way: print a row as a string instead of using nested for{} loops for a MXN printing procedure, or else you are guaranteed to get [Time Limit Exceeded](TLE). Actually the printing time is about 5-6 times more than the processing time.


p.s. If some1 have passed the Judge by using a recursive flooding algorithm in Java without the help of a list or array, pls call me a noob and post it here! I'll be more than happy to know that Java can do better

[alirezanoori]

WA! WA! WA!
I'm gonna kill myself! OMG! Please take a look at my program. I can't find ANYTHING wrong with it.
-I use iterative and VERY FAST method for flood fill.
-I tested my program with HUGE inputs and it worked excellent.
-I tested it with any kind of test data.
-I used my debug skills.
So it leaves me with this idea that I've done something silly again! I do this a lot and I hate myself for this. I wrote lots of programs on lots of online judges and every time I get WA I realize that something (for example a blank line) killed my code!!!! (
So here's my code.
Thank you guys for helping me out.

Code: Select all

#include <iostream>
#include <cmath>
#include <memory>
#include <queue>
using std::cout;
using std::endl;
using std::cin;
using std::queue;

char image[252][252];
int n, m;
char name[12];

enum Shape {HLINE, VLINE, RECT, REG};

#define ISGOOD(i,j) ((i > 0 && i <= m) && (j > 0 && j <= n) ? true : false)

void floodFillScanlineStack(int x, int y, char newColor, char oldColor)
{
    if(oldColor == newColor) return;
    queue< std::pair<int, int> > q;
   
    int y1;
    bool spanLeft, spanRight;

    std::pair<int, int> p;
    p.first = x;
    p.second = y;

    q.push(p);
   
    while(!q.empty())
    {
        p = q.front();
        x = p.first;
        y = p.second;
        q.pop();
        y1 = y;
        while(y1 >= 0 && image[x][y1] == oldColor) y1--;
        y1++;
        spanLeft = spanRight = false;
        while(y1 <= n && image[x][y1] == oldColor )
        {
            image[x][y1] = newColor;
            if(!spanLeft && x > 0 && image[x - 1][y1] == oldColor)
            {
                p.first = x - 1;
                p.second = y1;
                q.push(p);
                spanLeft = true;
            }
            else if(spanLeft && x > 0 && image[x - 1][y1] != oldColor)
            {
                spanLeft = false;
            }
            if(!spanRight && x <= m - 1 && image[x + 1][y1] == oldColor)
            {
                p.first = x + 1;
                p.second = y1;
                q.push(p);
                spanRight = true;
            }
            else if(spanRight && x <= m - 1 && image[x + 1][y1] != oldColor)
            {
                spanRight = false;
            }
            y1++;
        }
    }
}

void AddShape(int x1, int y1, int x2, int y2, char color, Shape sh)
{
    int i, j;
    char col;
   
    switch(sh)
    {
    case VLINE:
        if((y1 > y2) && (y1 != -1) && (y2 != -1))
            std::swap(y1, y2);
        for(i = y1; i <= y2; i++)
            image[i][x1] = color;
        break;
    case HLINE:
        if((x1 > x2) && (x1 != -1) && (x2 != -1))
            std::swap(x1, x2);
        for(i = x1; i <= x2; i++)
            image[y1][i] = color;
        break;
    case RECT:
        for(i = x1; i <= x2; i++)
        {
            for(j = y1; j <= y2; j++)
                image[j][i] = color;
        }
        break;
    case REG:
        col = image[y1][x1];
        floodFillScanlineStack(y1, x1, color, col);
        break;
    }
}

void printImage()
{
    cout << name << endl;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
            cout << image[i][j];
        cout << endl;
    }
}

void IgnoreLine()
{
    while(cin.get() != '\n');
}

int main()
{
    char command, c;
    int x1, x2, y1, y2;
    while(cin >> command)
    {
        if(command == 'X')
            break;

        switch(command)
        {
        case 'I': memset(image, 'O', sizeof image); cin >> n >> m; break;
        case 'C': memset(image, 'O', sizeof image); break;
        case 'L': cin >> x1 >> y1 >> c; image[y1][x1] = c; break;
        case 'V': cin >> x1 >> y1 >> y2 >> c; AddShape(x1, y1, -1, y2, c, VLINE); break;
        case 'H': cin >> x1 >> x2 >> y1 >> c; AddShape(x1, y1, x2, -1, c, HLINE); break;
        case 'K': cin >> x1 >> y1 >> x2 >> y2 >> c; AddShape(x1, y1, x2, y2, c, RECT); break;
        case 'F': cin >> x1 >> y1 >> c; AddShape(x1, y1, -1, -1, c, REG); break;
        case 'S': cin >> name; printImage(); break;
        default: IgnoreLine(); break;
        }

        while(iswspace(cin.peek()))
            cin.ignore();
    }
    return 0;
}