10267 - Graphical Editor

[RalphLoizzo]

Am I not following proper ettiquette here?

I'm looking for help on this problem.

[mf]

Well, you didn't mention what kind of problem you're having (WA, TLE, runtime error, etc.), and also, "If there is a thread about your problem, please use it."

Few people enjoy debugging code, and especially other people's code. If you made and posted some input cases, instead of code, and asked for correct output for them, I'm sure much more people would be willing to reply, and it will also be useful for others, who seek help.

Your implementation of flood fill seems wrong to me. What if color==oldcolor? As in the following test case:

Code: Select all

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


(Output should be the same as the sample output.)

[RalphLoizzo]

Thanks for 1) your help in this matter

2) explaining how best I can seek help using these forums.

I will work on your suggestion for this.

[shining]

i've got WA, and tested all the case in this board.
is there somebody can tell me why?

Code: Select all

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

int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
int M,N,top;
char canvas[250+2][250+2];

typedef struct _p { int x, y; } Px;
Px stack[250*250];

#define push(x) ( stack[++top]=x )
#define pop()   ( stack[top--]   )

typedef enum {
        Clear = 'C',
        Fill  = 'F',
        HDrow = 'H',
        New   = 'I',
        RDrow = 'K',
        PDrow = 'L',
        Save  = 'S',
        VDrow = 'V',
        Exit  = 'X'
} CMD;

void fill(int x, int y, char c, char rc);

int
main()
{
        char input[32];
        char *ptr, c;
        int i,j,x1,x2,y1,y2,tmp;

        while(1) {
                gets(input);

                ptr=&input[2];
                switch(input[0]) {
                case New:
                        sscanf(ptr,"%d %d",&M,&N);
                case Clear:
                        for(i=1;i<=N;i++) {
                                for(j=1;j<=M;j++) {
                                        canvas[i][j] = 'O';
                                        if(j==M)
                                                canvas[i][j+1]='\0';
                                }
                        }
                        break;
                case PDrow:
                        sscanf(ptr,"%d %d %c", &x1,&y1,&c);
                        if(x1<1||x1>M || y1<1||y2>N) break;
                        canvas[y1][x1]=c;
                        break;
                case HDrow:
                        sscanf(ptr,"%d %d %d %c",&x1,&x2,&y1,&c);
                        if(x1>x2) { tmp = x1; x1 = x2; x2 = tmp; }
                        if(x1<1||x2>M || y1<1||y1>N) break;
                        for(i=x1;i<=x2;i++)
                                canvas[y1][i]=c;
                        break;
                case VDrow:
                        sscanf(ptr,"%d %d %d %c",&x1,&y1,&y2,&c);
                        if(y1>y2) { tmp = y1; y1 = y2; y2 = y1; }
                        if(x1<1||x1>M || y1<1||y2>N) break;
                        for(i=y1;i<=y2;i++)
                                canvas[i][x1]=c;
                        break;
                case RDrow:
                        sscanf(ptr,"%d %d %d %d %c",&x1,&y1,&x2,&y2,&c);
                        if(x1>x2) { tmp = x1; x1 = x2; x2 = tmp; }
                        if(y1>y2) { tmp = y1; y1 = y2; y2 = tmp; }
                        if(x1<1||x2>M || y1<1||y2>N) break;
                        for(i=x1;i<=x2;i++)
                                for(j=y1;j<=y2;j++)
                                        canvas[j][i]=c;
                        break;
                case Fill:
                        sscanf(ptr,"%d %d %c",&x1,&y1,&c);
                        if(x1<1||x1>M || y1<1||y1>N ||
                                canvas[y1][x1]==c) break;
                        fill(x1,y1,c,canvas[y1][x1]);
                        break;
                case Save:
                        printf("%s\n",ptr);
                        for(i=1;i<=N;i++)
                                        printf("%s\n",&canvas[i][1]);
                        break;
                case Exit:
                        return 1;
                default:
                        break;
                }
        }
        return 1;
}

void
fill(int x, int y, char c, char rc)
{
        Px px,newpx;
        int i,tx,ty;

        px.x=x, px.y=y;
        canvas[y][x]=c;
        push(px);
        while(top>0) {
                px=pop();

                for(i=0;i<4;i++) {
                        tx=px.x+dir[i][0];
                        ty=px.y+dir[i][1];
                        if(canvas[ty][tx]==rc) {
                                canvas[ty][tx]=c;
                                newpx.x=tx;
                                newpx.y=ty;
                                push(newpx);
                        }
                }
        }
        return;
}


[Bandrosh]

UVA = Me Crazy

Code: Select all


Solved




[Bandrosh]

The Function (Check dos format ) is one copy of the oher source, i think this is the wa, but dont!!

[blodstone]

Almost crazy.
I have checked every test case and it seems fine for me. But i still got WA.
What's wrong with my program?

Code: Select all

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
using namespace std;

void fillRegion(int x, int y, char R,char C, char a[][250],bool val[][250],int m,int n){
   if(val[x-1][y]&&a[x-1][y]==R&&a[x-1][y]!=C&&x-1>=0&&x-1<=m&&y>=0&&y<=n){
      a[x-1][y]=C;
      val[x-1][y]=false;
      fillRegion(x-1,y,R,C,a,val,m,n);
   }

   if(val[x][y-1]&&a[x][y-1]==R&&a[x][y-1]!=C&&x>=0&&x<=m&&y-1>=0&&y-1<=n){
      a[x][y-1]=C;
      val[x][y-1]=false;
      fillRegion(x,y-1,R,C,a,val,m,n);
   }
   if(val[x+1][y]&&a[x+1][y]==R&&a[x+1][y]!=C&&x+1>=0&&x+1<=m&&y>=0&&y<=n){
      a[x+1][y]=C;
      val[x+1][y]=false;
      fillRegion(x+1,y,R,C,a,val,m,n);
   }
   if(val[x][y+1]&&a[x][y+1]==R&&a[x][y+1]!=C&&x>=0&&x<=m&&y+1>=0&&y+1<=n){
      a[x][y+1]=C;
      val[x][y+1]=false;
      fillRegion(x,y+1,R,C,a,val,m,n);
   }
}
int main(){
   //freopen("input.in","r",stdin);
   //freopen("output.out","w",stdout);
   char X,c;
   int m, n, x1, x2, y1, y2, x, y;
   char a[250][250];
   char name[12];
   while(cin >> X && X!='X'){
      if(X=='I'){
         cin >> n >> m;
         for(int i=0;i<250;i++){
            for(int j=0;j<250;j++){
               a[i][j]='O';
            }
         }
      }
      else if(X=='C'){
         for(int i=0;i<250;i++){
            for(int j=0;j<250;j++){
               a[i][j]='O';
            }
         }
      }
      else if(X=='L'){
         cin >> y >> x >> c;
         a[x-1][y-1]=c;
      }
      else if(X=='V'){
         cin >> x >> y1 >> y2 >> c;
         for(int j=y1-1;j<y2;j++){
            a[j][x-1]=c;
         }
      }
      else if(X=='H'){
         cin >> x1 >> x2 >> y >> c;
         for(int j=x1-1;j<x2;j++){
            a[y-1][j]=c;
         }
      }
      else if(X=='K'){
         cin >> y1 >> x1 >> y2 >> x2 >> c;
         if(x2>m) x2=m;
         if(y2>n) y2=n;
         for(int i=x1-1;i<x2;i++){
            for(int j=y1-1;j<y2;j++){
               a[i][j]=c;
            }
         }
         
      }
      else if(X=='F'){
         cin >> y >> x >> c;
         char R = a[x-1][y-1];
         bool val[250][250];
         for(int i=0;i<250;i++){
            for(int j=0;j<250;j++){
               val[i][j]=true;
            }
         }
         if(R!=c && y<=n && x<=m)
         fillRegion(x-1,y-1,R,c,a,val,m-1,n-1);
      }
      else if(X=='S'){
         cin >> name;
         cout << name << endl;
         for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
               cout << a[i][j];
            }
            cout << endl;
         }
      }
      else{
         char buff[100];
         cin.getline(buff,100);
      }
   }
}

[klopyrev]

There is a test case where X1 > X2 or Y1 > Y2! Correct for that and I think it should work! Tell me how it goes!

[blodstone]

Thanks, it seems that my flood fill has messed up a little bit besides that I also have fixed the X2<X1 problem. I swap both value if X2<X1 and now I got an AC.

[dzhus]

Hello, guys. I was struggling really hard to get this program done. Here are some tips that I can give:
1. If you are using BOOK (programming challanges or other), especially if it is in Russian language (I read this one) BE AWARE OF THE MISTAKE IN IT. The mistake is in DRAW FILLED RECTANGLE command. IT SHOULD BE LIKE THIS: K X1 Y1 X2 Y2 COLOR, but in the book it is K X1 X2 Y1 Y2 C.
2. In H and V commands X1 is not necessary greater than X2 and Y1 is not neccessary greater than Y2
3. I dont know if there are unpredicted tests, but the only place where I checked for additional mistakes (I mean in addition to one discribed in the text of the problem) was in FILL_REGION. I used something like this:
if(x<1 || x>M || y<1 || y>N)
return;
4. I used iterative algorithm, but some people say that the recursive one is also OK (see other topics of this program issue). By the way, if you are interested in iterative logic, you can find it here http://online-judge.uva.es/board/viewtopic.php?t=10168. I used one very similar to this one.
This's probably it.
Good luck.

[soff]

Please have a look at the following code, it has passed test cases I found on the forum, but still gets WA...

Code: Select all

#include <stdio.h>

#define MAX 252

char canvas[MAX][MAX];
int m, n;

void create() {
   int i, j;

   scanf("%d %d", &m, &n);

   for (i = 0; i < n; i++) {
      for (j = 0; j < m; j++) {
         canvas[i][j] = 'O';
      }
   }

   return;
}

void color() {
   int i, j;

   for (i = 0; i < n; i++) {
      for (j = 0; j < m; j++) {
         canvas[i][j] = 'O';
      }
   }

   return;
}

void line() {
   int x, y;
   char c;

   scanf("%d %d %c", &x, &y, &c);

   canvas[y - 1][x - 1] = c;

   return;
}

void vline() {
   int x, y1, y2;
   char c;
   int i;
   int a, b;

   scanf("%d %d %d %c", &x, &y1, &y2, &c);

   a = y1 > y2 ? y2 : y1;
   b = y1 > y2 ? y1 : y2;

   for (i = a; i <= b; i++) {
      canvas[i - 1][x - 1] = c;
   }

   return;
}

void hline() {
   int x1, x2, y;
   char c;
   int i;
   int a, b;

   scanf("%d %d %d %c", &x1, &x2, &y, &c);

   a = x1 > x2 ? x2 : x1;
   b = x1 > x2 ? x1 : x2;

   for (i = a; i <= b; i++) {
      canvas[y - 1][i - 1] = c;
   }

   return;
}

void rectangle() {
   int x1, x2, y1, y2;
   char c;
   int i, j;
   
   scanf("%d %d %d %d %c", &x1, &y1, &x2, &y2, &c);
   
   for (i = x1; i <= x2; i++) {
      for (j = y1; j <= y2; j++) {
         canvas[j - 1][i - 1] = c;
      }
   }
   
   return;
}

void fillrec(int x, int y, int oc, int c) {
   canvas[x - 1][y - 1] = c;
   
   if (x > 1) {
      if (canvas[x - 2][y - 1] == oc) {
         fillrec(x - 1, y, oc, c);
      }
   }
   
   if (y > 1) {
      if (canvas[x - 1][y - 2] == oc) {
         fillrec(x, y - 1, oc, c);
      }
   }
   
   if (x < n) {
      if (canvas[x][y - 1] == oc) {
         fillrec(x + 1, y, oc, c);
      }
   }
   
   if (y < m) {
      if (canvas[x - 1][y] == oc) {
         fillrec(x, y + 1, oc, c);
      }
   }
   
   return;
}

void fill() {
   int x, y, oc;
   char c;
   
   scanf("%d %d %c", &x, &y, &c);
   oc = canvas[x - 1][y - 1];
   
   if (oc == c)
      return;
   
   fillrec(x, y, oc, c);
   
   return;
}

void name() {
   char fname[12];
   int i, j;
   
   scanf("%s", fname);

   printf("%s\n", fname);

   for (i = 0; i < n; i++) {
      for (j = 0; j < m; j++) {
         printf("%c", canvas[i][j]);
      }
      printf("\n");
   }
   
   return;
}

int main() {
   char k;

   while ((k = getchar()) != 'X') {
      switch (k) {
         case 'I':
            create();
            break;
         case 'C':
            color();
            break;
         case 'L':
            line();
            break;
         case 'V':
            vline();
            break;
         case 'H':
            hline();
            break;
         case 'K':
            rectangle();
            break;
         case 'F':
            fill();
            break;
         case 'S':
            name();
            break;
         default:
            while (getchar() != '\n');
      }
   }

   return 0;
}


[lucaskt]

I haven't really solved it myself yet, but I can spot a problem right away: iIn the name function, fname needs 13 chars because of the terminator.

Cheers,
Lucas

[wes]

I have been working on this problem for a long time, but I'm getting WA at programming-challenges.com and RTE(11) at acm.uva. I think I saw almost all threads, but I can't get AC. Here is my code:

Code: Select all

#include <stdio.h>

typedef struct point_{
  int x;
  int y;
  int visited;
}point;

char image[256][256];

void swap(int * p, int * q){
  int tmp;
  tmp = *p;
  *p = *q;
  *q = tmp;
} 
void I(int m, int n){
  int X,Y;
  for(Y=1;Y<=n;Y++){
    for(X=1;X<=m;X++)
      image[Y][X]='O';
  }
}

void C(int m, int n){
  int X,Y;
  for(Y=1;Y<=n;Y++){
    for(X=1;X<=m;X++)
      image[Y][X]='O';
  }
}
void L(int m, int n, int x, int y, char  c){
  if(x<=m && y<=n && c<=90){
    image[y][x]=c;
  }
}

void V(int m, int n,int x, int y1, int y2, char c){
  int Y;
  if(x<=m && y1<=n && y2<=n && c<=90){   
    if(y2<y1)
      swap(&y1,&y2);
    for(Y=y1;Y<=y2;Y++)
      image[Y][x]=c;
  }
}

void H(int m, int n,int x1, int x2, int y,char c){
  int X;
  if(x1<=m && x2<=m && y<=n && c<=90){     
    if(x2<x1)
      swap(&x1,&x2); 
    for(X=x1;X<=x2;X++)
      image[y][X]=c;
  }
}
void K(int m, int n,int x1, int y1, int x2, int y2 ,char c ){
  int X,Y;
  if(x1<=m && x2>=1&& y1<=n && y2<=n && c<=90){   
    if(y2<y1)
      swap(&y1,&y2);
    if(x2<x1)
      swap(&x1,&x2);
    for(Y=y1;Y<=y2;Y++){
      for(X=x1;X<=x2;X++)     
   image[Y][X]=c;
    }
  }
}

void F(int m, int n, char c_atual, int x_, int y_,char c){
 
 
  point points[62505];
  int p;
  int actual_p;
  int X, Y;
  int x, y;
 
  for(X=0;X<600;X++){
    points[X].visited=0;
  }
 
  p=0;
  actual_p=0;
 
  x=x_;
  y=y_;
 
  image[y][x]=c;
  points[p].x=x;
  points[p].y=y;
  p++;
 
  while(actual_p<=p){
    x = points[actual_p].x;
    y = points[actual_p].y;     
 
    if(!points[actual_p].visited){
           
      for(X=x+1; X<=m && image[y][X]==c_atual ;X++){
   image[y][X]= c;
   points[p].x = X;
   points[p].y= y;
   p++;
      }
     
      for(X=x-1; X>=1 && image[y][X]==c_atual ; X--){
   image[y][X]= c;
   points[p].x = X;
   points[p].y= y;
   p++;
      }
      for(Y=y-1;Y>=1 && image[Y][x]==c_atual ; Y--){
   image[Y][x]= c;
   points[p].x  = x;
   points[p].y  = Y;
   p++;
      }
      for(Y=y+1;Y<=n && image[Y][x]==c_atual;Y++){
   image[Y][x]= c;
   points[p].x  = x;
   points[p].y  = Y;
   p++;
      }
      points[actual_p].visited = 1;
    }
   
    actual_p++;   
  }

 
}
void S(int m, int n, char *name){
  int X,Y; 
 
  printf("%s\n", name); 
  for(Y=1;Y<=n;Y++){
    for(X=1;X<=m;X++)     
      printf("%c",image[Y][X]);
    printf("\n");   
  }
}

int main(){
 
  char command;
  char name[16];
  int m, n;
  int x, y, x1, x2, y1, y2;
  char c; 
  while(1){
    scanf("%c", &command);       
    if(command =='X')
      break;   
    switch(command){
    case 'I':     
      scanf("%d %d", &m, &n);
      I(m,n);     
      break;
    case 'C':
      C(m,n);
      break;
    case 'L':
      scanf("%d %d %c\n",&x, &y, &c);
      L(m,n,x,y,c);
      break;
    case 'V':
      scanf("%d %d %d %c\n", &x, &y1, &y2, &c);
      V(m,n,x, y1, y2,c);   
      break;
    case 'H':
      scanf("%d %d %d %c\n", &x1, &x2, &y, &c);     
      H(m,n,x1,x2,y,c);   
      break;
    case 'K':
      scanf("%d %d %d %d %c\n", &x1,&y1,&x2,&y2,&c);         
      K(m,n,x1,y1,x2,y2,c);
      break;
    case 'F':
      scanf("%d %d %c\n", &x,&y,&c);               
      F(m,n,image[y][x],x,y,c);
      break;
    case 'S':
      scanf("%s",name);
      S(m,n,name);
      break;     
    }   
  }
  return 0;
}


Thnks in advance!


PS.. sorry the poor english!

[wes]

Or some tricky test cases would be very usefull.

[Cheetahfoot]

This is an annoying as hell problem, but I managed to get it in three tries.

First of all, ignore everyone who says that the recursive flood fill won't work. Properly coded, it works fine. So if you're sweating out an iterative version, don't bother. The iterative version is less intuitive for this problem and is more work than necessary (unless you're working on some specific optimization and the iteration is mandatory for that).

Secondly, someone makes the point about making sure your individual commands are properly coded. That *is* crucial. Off-by-one errors can kill your algorithm easily. Don't bother scamming around for sample datasets. I don't have any and it doesn't look like anyone else is going to come up with them either. Instead, test your own individual commands according to the following criteria:

1. Does the command work at the boundaries of the image?

2. Does my implementation work at all the boundary conditions of the problem statement?

3. Is any given command repeatable over the same coordinates (especially important for the flood fill)? It should be.

4. Certain commands *must* have the parameters' values given in the right order for the command to make any sense. But there are some commands for which different orderings of the parameters' values do not constitute an error. Be sure, for these commands, that you check the values for sanity. Notice that I'm saying the parameters' *values*, not the parameters themselves, which must always be in the correct order.

5. If you're using a recursive flood fill, are you absolutely certain that the function will never enter an infinitely recursive state? In other words, are you returning from the function on all the appropriate end conditions? Are you *sure*?

6. If you're using an iterative flood fill, are you certain you're checking all side-to-side values (not diagonal)? Are staying within the image boundaries?

7. Finally, could your implementation be simpler? Simulations frequently seem like they should be more complicated than they are. The questions you should be asking are, do I really need a struct to represent a point? Do I need any custom data structures at all? Do they truly make the code simpler? And so on ...

This seems like a frustrating problem, but it's totally solvable. Just go through the list and be meticulous about the code and the problem statement, and you'll get it.