10267 - Graphical Editor

[Darko]

Do you check that, for instance, Y1 might be greater than Y2 (or X1 > X2)? That would be a common mistake. Other than that, it should be straight-forward. Tedious, but straight-forward.

Check your WA times with other times. If it's extremely shorter, it might be a RTE, but OJ doesn't report it as such.

Sorry I can't be any more specific, but, again, I don't know what you've done so far.

Darko

[tOd]

oh~ great!!
I found solution in my mistake.
it was found in relationless code.
Thanks Darko for advice!!

[mcgeun]

I don't know why i got run time error.
this is my code.

Code: Select all

/*
runtime error;
vc6.0 : I 150+ 150+, F X Y COLOR => EXCEPTION !
BUT cygwin -> not exception;
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int row, col;
char table[251][251];
char color, color2;

void myfunc(int x, int y) {
   table[y][x] = color;
   if ((x+1 <= col) && (table[y][x+1] == color2)) {
      myfunc(x+1, y);
   }
   if ((x-1 >= 1) && (table[y][x-1] == color2)) {
      myfunc(x-1, y);
   }
   if ((y+1 <= row) && (table[y+1][x] == color2)) {
      myfunc(x, y+1);
   }
   if ((y-1 >= 1) && (table[y-1][x] == color2)) {
      myfunc(x, y-1);
   }
}

void main()
{
   char buf[82];
   char filename[13];
   int i, j;
   char cmd;
   int x, y;
   int x1, y1, x2, y2;
   int temp;
   int flag = 1;


   while (flag && fgets(buf, sizeof(buf), stdin)) {
      switch (buf[0]) {
      case 'I':
         sscanf(buf, "%c %d %d", &cmd, &col, &row);
         /* no break; */
      case 'C':
         for (i=1; i<=row; i++) {
            for (j=1; j<=col; j++) {
               table[i][j] = 'O';
            }
         }
         break;
      case 'L':
         sscanf(buf, "%c %d %d %c", &cmd, &x, &y, &color);
         table[y][x] = color;
         break;
      case 'V':
         sscanf(buf, "%c %d %d %d %c", &cmd, &x, &y1, &y2, &color);
         if (y1 > y2) {
            temp = y1;
            y1 = y2;
            y2 = temp;
         }
         for (i=y1; i<=y2; i++) table[i][x] = color;
         break;
      case 'H':
         sscanf(buf, "%c %d %d %d %c", &cmd, &x1, &x2, &y, &color);
         if (x1 > x2) {
            temp = x1;
            x1 = x2;
            x2 = temp;
         }
         for (i=x1; i<=x2; i++) table[y][i] = color;
         break;
      case 'K':
         sscanf(buf, "%c %d %d %d %d %c", &cmd, &x1, &y1, &x2, &y2, &color);
         for (i=y1; i<=y2; i++)
            for (j=x1; j<=x2; j++)
               table[i][j] = color;
         break;
      case 'F':
         sscanf(buf, "%c %d %d %c", &cmd, &x, &y, &color);
         color2 = table[y][x];
         myfunc(x, y);
         break;
      case 'S':
         sscanf(buf, "%c %s", &cmd, filename);
         printf("%s\n", filename);
         for (i=1; i<=row; i++) {
            for (j=1; j<=col; j++) {
               printf("%c", table[i][j]);
            }
            printf("\n");
         }
         break;
      case 'X':
         flag = 0;
         break;
      default:
         break;
      }
   }
}


thanks for read.
if you know the reason, tell me please.

[sclo]

It is clear that recursive fill function (floodfill) will get AC if we actually check to see if the new color is equal to the old color. For example:

Code: Select all

void fill(int i,int j,char color) {
  char oldcolor = M[i][j];
  if(oldcolor==color)
    return;
  M[i][j]=color;
  for(int k=0; k<4; k++) {
    int ii=i+di[k],jj=j+dj[k];
    if(ii>=0&&ii<m&&jj>=0&&jj<n&&M[ii][jj]==oldcolor)
      fill(ii,jj,color);
  }
}


There's no need to get fancy with fill. If we don't check that old color is equal to new color, then stack overflow will guarantee to occur, resulting in RTE[/code]

[fayyazkl]

Hi i am new to this domain! but not to programming
Here is my code! can any body tell why is it getting WA or atleast suggest an input that fails. I shall be really grateful!


# include <iostream>
# include <cstdio>
using namespace std;

char image[250][250];
int n,m;
void fill (int, int, char,char);
int checksub (int,int);

main ()
{

char comm, color, old;
int i,j,x,y,y1,y2,x1,x2,temp;
char name [13];
cin >> comm;
if (comm == 'I')
{
cin >> m >> n;
for (i=0; i< n;i++)
for (j=0; j<m; j++)
image[i][j]= 'O';
}

while (comm != 'X')
{

cin >> comm;
if (comm!='I'&& comm!='C'&& comm!='L' && comm!='V' && comm!='H'&& comm!='K'&& comm!='F'&& comm!='S' && comm!='X')
{
char temp1 [50];
gets (temp1);
}
switch (comm)
{
case 'I':
cin >> m >> n;
for (i=0; i<n;i++)
for (j=0; j<m; j++)
image[i][j]= 'O';
break;

case 'C':
for (i=0; i<n;i++)
for (j=0; j<m; j++)
image[i][j]= 'O';
break;

case 'L':
cin >> y >> x >> color;
image[x-1][y-1]= color;
break;

case 'V':
cin >> x >> y1 >> y2 >> color;

if (y1 > y2)
{
temp = y1;
y1=y2;
y2=temp;
}
for (i=y1;i<=y2;i++)
image[i-1][x-1] = color;
break;

case 'H':
cin >> x1 >> x2 >> y >> color;

if (x1 > x2)
{
temp = x1;
x1=x2;
x2=temp;
}
for (i=x1; i<=x2; i++)
image[y-1][i-1] = color;
break;
case 'K':
cin >> x1 >> y1 >> x2 >> y2 >> color;
for (i=y1-1; i<y2; i++)
for (j=x1-1; j<x2; j++)
image[i][j] = color;
break;

case 'F':
cin >> x >> y >> color;

old = image[y-1][x-1];
if (old == color) // if old color is same as new
break;

else fill (y-1,x-1,old,color);
break;

case 'S':
cin >> name;
cout << name;
for (i=0; i<n;i++)
{
cout << endl;
for (j=0; j<m; j++)
cout << image[i][j];
}
cout << endl;
break;
}
}
return 0;
}


void fill (int row, int col, char oldcolor, char newcolor)
{


if (oldcolor == image[row][col]) // if neighbor matches old fill it with new
image[row][col] = newcolor;
else return;

if ( checksub (row,col-1) == 0 )
fill(row,col-1,oldcolor, newcolor);
if ( checksub (row-1,col) == 0 )
fill(row-1,col, oldcolor, newcolor);
if ( checksub (row+1,col) == 0 )
fill(row+1,col,oldcolor, newcolor);
if ( checksub (row,col+1) == 0 )
fill(row,col+1,oldcolor, newcolor);

}

int checksub(int x, int y)
{
if (x >=0 && x<n && y>=0 && y<m)
return 0;
else return 1;

}

[fayyazkl]

Its been a long time since i have submitted this problem. The only progress is that i now KNOW THAT MY PROGRAM FAILS ON FLOOD FILL IF THE SIZE OF THE IMAGE GETS GREATER THAN 101 x 101. The program gets terminated. I have heard that recursive function is okay. And i wrote it. Secondly, i dont seem to find an iterative logic for this function. Please help me readers.

[Jan]

Just try the I/O set..

Inout:

Code: Select all

I 5 6
L 2 3 A
S one.bmp
G 2 3 J
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
F 3 3 J
S two.bmp
X

Output:

Code: Select all

one.bmp
OOOOO
OOOOO
OAOOO
OOOOO
OOOOO
OOOOO
two.bmp
JJJJJ
JJZZJ
JWJJJ
JWJJJ
JJJJJ
JJJJJ

Hope it helps.

[John Herre]

I've read most of your code, some sugestions:

First:

I don't like - just a matter of taste ; ) - the cin >> comm; that is preceding the main loop, the structure of my program is like this:

Code: Select all

flag = true;
do
{
   cin >> comm;
   if( comm == 'X' )
      flag = false;
   if( flag && comm != ' ' )  // process the command, the ' ' is because the text for the //problem says: ... "in the very beginning of the line" so I //thought they are using "non-valid" space-started command lines...
   {
      //here goes the switch - case...
   }
}while( flag );



The reason I'm criticizing the structure of your program is because, actually, you are doing:

cin >> comm;

twice, I suggest you to consider rewriting the structure ; ) !

Second:

Code: Select all

   case 'L':
     cin >> y >> x >> color;
     image[x-1][y-1]= color;
     break;


the way you're using your array forces you to consider the second index as the X-related. So, the right must be:

Code: Select all

   image[y-1][x-1] = color;


Third:

I didn't check your recursive function, but I solved it using an iterative way, here it is:


The region R to be filled is defined as follows. The pixel (X,Y) belongs to this region. The other pixel belongs to the region R if and only if it has the same colour as pixel (X,Y) and a common side with any pixel which belongs to this region.


Well, following this definition, my algorithm is this:

Code: Select all

   - By definition (X,Y) belongs to R.
   ---> then let's create a vector which holds this pixel, this vector is called R

do
{

   - Now, every pixel, sharing sides with at least one of the pixels in R and being the same color, belongs to R. But.... not so fast, let's create another vector, called "conexos" (It's spanish, I'm Colombian :D ) in which I will store the pixels who share one side with at least one of the pixels stored in R, and have the same color, of course.

   - Let's fill the pixels stored in R. For every pixel stored in R, perform a single-pixel fill.

   - Empty R.

   - Swap the data between R and conexos.

} while( R.size > 0 );


By now you are being carefull in searching for connected pixels, because only 4 of the 9 around a given pixel can be tested.


There're at least two subtle things you must take care in this solution, but I will let you look for them...


That's all, I hope this helps you!

I'll be waiting for good new from you on this topic. Happy programming!!

P.D. I'm very happy, because this is the first problem I get AC on first try! I sent it just a couple of hours ago!!

[John Herre]

Maybe this could help you:

http://online-judge.uva.es/board/viewto ... 7764#47764

jedihe

[fayyazkl]

Hi John!

Thnx alot for your help! I have really been tired of this problem as it simply doesnt seem to work my way. I have followed all the points you have told me.

First, the convention of using cin twice doesnt matter in this problem. That i can tell you from my experience on this online judge. They dont have multiple blank lines unless stated!

Secondly, (the L command) the way i am using my arrays is correct according to syntax. You can verify it by giving an input set 2,3 or 3,2 as it gives the columns first.

The fill function (my worst nighmare ). I have followed your suggested logic. I am not very proficient with STL since i dont use it often. Primarily coz its difficult to debug in Visual C++ 6 editor. However, i have made my effort with vector class and after having some syntax problem i have finally come up with a version of code. But it still fails! i dont know what goes wrong but it works on a small input and crashes on larger ones. Please check it out and help me. I have never spent this much time on a problem and this was among the ones that i solved in my very early times on this site. (user id 37504 ranked 3100 76 solved)

here is the code (only the F command)
I made a struct named
struct loc
{
int xc,yc
};

case 'F':
cin >> x >> y >> newcolor;

oldcolor = image[y-1][x-1];
if (oldcolor == newcolor) // if old color is same as new
break;


else
{
vector <loc> R,nbr;
struct loc temp;

temp.xc=y-1;
temp.yc=x-1;

R.push_back(temp);

while (R.size()>0)
{
// filling image at R locations
// with new color
for (int p=0; p<R.size(); p++)
{
temp = R[p];
image[temp.xc][temp.yc]=newcolor;
}

// loop that copies the immediate valid
// nbrs into neighbour array

for (int s=0; s<R.size(); s++)
{
temp = R[s];

if ( temp.xc-1 >= 0 &&
image[temp.xc-1][temp.yc]==oldcolor)
{
temp.xc = temp.xc-1;
nbr.push_back(temp);
}

if (temp.yc-1 >= 0 &&
image[temp.xc][temp.yc-1]==oldcolor)
{
temp.yc = temp.yc-1;
nbr.push_back(temp);
}

if (temp.xc+1 < n &&
image[temp.xc+1][temp.yc]==oldcolor)
{
temp.xc = temp.xc+1;
nbr.push_back(temp);
}

if (temp.yc+1 < m &&
image[temp.xc][temp.yc+1]==oldcolor)
{
temp.yc = temp.yc+1;
nbr.push_back(temp);
}
}

// empty R and copy neigbours into R
//R.erase(R.begin(),R.end());
R.clear();

if (R.empty())
R = nbr;
nbr.clear();
}
}

//fill (y-1,x-1);
break;

[John Herre]

Well, I have read your code, I hand-tested it. I found this problem:

when you are looking for a neighbour pixel for the current one, you must do that this way:

Code: Select all

   .......
   ...n...
   ..nRn..
   ...n...
   .......


But, in the 'worst' case, your search is being performed this way:

Code: Select all

   .......
   ..nn...
   ..nR...
   .......
   .......


I mean the worst case when all the surrounding pixels are the same color as the one where the flood fill started. The reason this happens is because you are modifying the coordinate values in temp. I suggest you to reassign temp before every step looking around. Maybe that will make your code work.

jedihe

P.D. I also recommend to use the swap() function instead of reassigning the vector identifiers.

P.D. Good reference for STL: http://www.cppreference.com/

[fayyazkl]

Hello John!

FINALLLY FINALLY its DONE!!!!!(ACC) Thank you Allah Almighty!!
I am really thankful to you john for extending your help. Since the day i started the board i admit that i do get help from EXISTING POSTS but so far, it has been very rare that some body in particular helped or responded me. I had a feeling that perhaps that have some community sorts of things and people usually bother helping others which are already known to them in some respect. I might be wrong on this but this was my experience!!

U have been the first one to have responded this much and i am successful using ur suggested iterative logic. It was not just one problem. It was among my failure points. I am quite an experienced programmer and this problem really drove me crazy and i used to feel ashamed on myself sort of... since i had spent quite a long time with this... but thanx to you who came to my rescue. I saw that you are relatively new to this board. Feel free to ask of any problem that u might face and need any help that i can provide.

Lastly, the approach thing apart from what u mentioned about not looking for the right neighbors in the worst case. I had another problem with my code and that was....
if scenario is this
..
..
fill funtion in four elements then it marks one element twice for the second array. I corrected it and got acc.

Best regards

[John Herre]

...any help that i can provide.

Of course, I'll be looking for help in case I need it...

Fayyaz, It was a pleasure to help you. It's cool to see the number 10267 in your personal statistics...

jedihe

[RalphLoizzo]

Couldnt understand the statement on the fill method on the problem. I didnt know what was meant by a side?!?!

Thinking of a pixel as a dot(not a square with sides) really confused me. Thanks for the clarification.

[RalphLoizzo]

What could be the problem?

Here's my sourcecode

Code: Select all

#include <stdio.h>
int xcounter, ycounter; /*      Simple counting vars */
int x1, x2, y1, y2, swap;               /*      Coordinates used in commands */
int C=260, R=260;                               /*      M is num of columns, N is num of rows */
char cmd;                               /*      Actual command to be processed */
char color, oldcolor;                           /*      The color stored in the image array */
char filename[255];             /*      Place to the store the file name string */
int rows=260;                   /*      Maximum number of rows */
int cols=260;                   /*      Maximum number of columns */
char image[260][260];           /*      Array to hold the image */
int tempx, tempy;
char tempnewcolor, tempoldcolor;

void floodfill(tempx, tempy, tempnewcolor, tempoldcolor)
{
        /*      Is this a legal pixel */
        if ((tempx<1)||(tempx>C)||(tempy<1)||(tempy>R))
                return;

        if (image[tempy][tempx]==tempoldcolor)
        {
                image[tempy][tempx]=tempnewcolor;
                floodfill(tempx+1,tempy,tempnewcolor,tempoldcolor);
                floodfill(tempx-1,tempy,tempnewcolor,tempoldcolor);
                floodfill(tempx,tempy+1,tempnewcolor,tempoldcolor);
                floodfill(tempx,tempy-1,tempnewcolor,tempoldcolor);
        }
        else
        {
                return;
        }
}

int main(int argc, char *argv[])
{

        while (1)
        {

                /* Read in a command */

                scanf("%c", &cmd);

                switch(cmd)     /* Process the input */
                {
                case    'X':
                        return 0;       /* End the program */
                        break;
                case    'I':
                        /*      Create a new image and init to white (O) */
                        scanf("%d %d",&C, &R);
                        for (ycounter=1;ycounter<=R;ycounter++)
                        {
                                for (xcounter=1;xcounter<=C;xcounter++)
                                {
                                        image[ycounter][xcounter]='O';
                                }
                        }
                        break;
                case    'C':
                        /*      Clear the table already made to white */
                        for (ycounter=1;ycounter<=R;ycounter++)
                        {
                                for (xcounter=1;xcounter<=C;xcounter++)
                                {
                                        image[ycounter][xcounter]='O';
                                }
                        }
                        break;
                case    'L':
                        /*      Get the pixel then color it */
                        scanf("%d %d %c",&x1, &y1, &color);
                        image[y1][x1]=color;
                        break;
                case    'V':
                        /*      Draw a vertical segment of color in X, between
                                rows y1 and y2 inclusive        */
                        scanf("%d %d %d %c",&x1,&y1,&y2,&color);
                        if (y1<=y2)
                        {
                                for(ycounter=y1;ycounter<=y2;ycounter++)
                                        image[ycounter][x1]=color;
                        }
                        else
                        {
                                for(ycounter=y2;ycounter<=y1;ycounter++)
                                        image[ycounter][x1]=color;
                        }
                        break;
                case    'H':
                        /*      Draw a horizontal segment of color in Y between cols
                                x1 and x2 inclusive     */
                        scanf("%d %d %d %c",&x1,&x2,&y1,&color);
                        if (x1<=x2)
                        {
                                for(xcounter=x1;xcounter<=x2;xcounter++)
                                        image[y1][xcounter]=color;
                        }
                        else
                        {
                                for(xcounter=x2;xcounter<=x1;xcounter++)
                                        image[y1][xcounter]=color;
                        }
                        break;
                case    'K':
                        /*      Draw a filled in rectangle of color     */
                        scanf("%d %d %d %d %c",&x1,&x2,&y1,&y2,&color);
                        /*      What follows here is a way to always go from 1
                                end to the other, no matter which number is
                                bigger than the other   */
                        for     (ycounter=y1;
                                ((y1<=y2)?(ycounter<=y2):(ycounter>=y2));
                                ((y1<=y2)?(ycounter++):(ycounter--)) )
                                {
                                        for (xcounter = x1;
                                                ((x1<=x2)?(xcounter<=x2):(xcounter>=x2));
                                                ((x1<=x2)?(xcounter++):(xcounter--)) )
                                                {
                                                        image[ycounter][xcounter]=color;
                                                }
                                }
                        break;
                case    'F':
                        /*      Perform the notorious flood fill */
                        scanf("%d %d %c",&x1,&y1,&color);
                        oldcolor=image[y1][x1];
                        floodfill(x1,y1,color,oldcolor);
                        break;
                case    'S':
                        color=getchar();
                        gets(filename);
                        printf("%s\n",filename);
                        for (ycounter=1;ycounter<=R;ycounter++)
                                {
                                        for (xcounter=1;xcounter<=C;xcounter++)
                                        {
                                                printf("%c",image[ycounter][xcounter]);
                                        }
                                        printf("\n");
                                }
                        break;

                }
        }



        return 0;
}