OJ Board

Posted: **Thu Aug 31, 2006 7:42 pm**

What could be the problem?

Here's my sourcecode

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

Posted: **Thu Sep 07, 2006 4:57 pm**

Am I not following proper ettiquette here?

I'm looking for help on this problem.

Posted: **Thu Sep 07, 2006 11:53 pm**

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

Posted: **Sat Sep 09, 2006 9:44 pm**

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.

Posted: **Sat Sep 23, 2006 9:45 pm**

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

Posted: **Thu Dec 21, 2006 2:10 am**

UVA = Me Crazy

Code: Select all


Solved

Posted: **Thu Dec 21, 2006 2:12 am**

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

Posted: **Mon Dec 25, 2006 8:02 pm**

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

Posted: **Tue Dec 26, 2006 10:39 am**

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!

Posted: **Tue Dec 26, 2006 1:56 pm**

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.

Posted: **Sat Feb 03, 2007 1:21 am**

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.

Posted: **Wed Mar 14, 2007 10:51 am**

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

Posted: **Thu Mar 15, 2007 1:08 am**

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

Posted: **Mon May 21, 2007 8:35 pm**

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!

Posted: **Mon May 21, 2007 8:41 pm**

Or some tricky test cases would be very usefull.

OJ Board

10267 - Graphical Editor

10267 Graphical Editor

Does anyone read these any more?

Proper Ettiquette!

10267 Graphical Editor WA!

10267 I

10267 - Graphical Editor