10267 - Graphical Editor

[carneiro]

My solution is exactly like yours, but i'm getting Sigsegv .

I'm trying to find out why. Have you got Sigsegv for this ?

[oriol78]

no, just WA

[carneiro]

I've fixed my SIGSEV, just a switched X Y in one of the coloring functions ... now it's WA

It looks exactly like yours now. I've made this test :

Code: Select all

I 5 6
L 2 3 A
S one.bmp
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
S two.bmp
I 50 50
C
F 10 10 B
S TESTE0.KAR
H 1 10 2 X
S TESTE1.KAR
V 5 1 10 X
S TESTE.FUL
F 5 2 U
S TESTE2.FOI
C
S TESTE3.Fix
K 5 5 25 25 X
S BLA
V 15 5 25 B
H 5 25 15 B
S BLE
L 15 7 I
S BLI
L 15 9 X
S BLO
F 7 7 I
S BLU
X

And it was ok ... The last output was :

Code: Select all

BLU
00000000000000000000000000000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIIIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIIIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000IIIIIIIIIIBIIIIIIIIII0000000000000000000000000
0000BBBBBBBBBBBBBBBBBBBBB0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
0000XXXXXXXXXXBXXXXXXXXXX0000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
                                                                

[/code]

[carneiro]

I getting WA with this problem, and I've tested it in every possible way i've foreseen

Could somebody put in some test data ?

My test is :

Code: Select all

I 5 6
L 2 3 A
S one.bmp
F 3 3 J
V 2 3 4 W
H 3 4 2 Z
S two.bmp
I 50 50
C
F 10 10 B
S TESTE0.KAR
H 1 10 2 X
S TESTE1.KAR
V 5 1 10 X
S TESTE.FUL
F 5 2 U
S TESTE2.FOI
C
S TESTE3.Fix
K 5 5 25 25 X
S BLA
V 15 5 25 B
H 5 25 15 B
S BLE
L 15 7 I
S BLI
L 15 9 X
S BLO
F 7 7 I
S BLU
H 1 50 50 M
V 50 1 50 M
S TEC
F 1 49 S
S TOC
X

and my LAST output (of course, for the sake of simplicity) is :

Code: Select all

SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIIIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIIIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSIIIIIIIIIIBIIIIIIIIIISSSSSSSSSSSSSSSSSSSSSSSSM
SSSSBBBBBBBBBBBBBBBBBBBBBSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSXXXXXXXXXXBXXXXXXXXXXSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSM
MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

Is there anything wrong with this ?
Could you post the input data you used ?

thanks !

[oriol78]

yes, i have the same output, and i have got WA too

[Sebasti]

Hi,

There is an error in your output. When you create an empty table or clear the current table, you must fill it with 'O' (capital letter O), not 0 (digit 0).
Furthermore, the other topic about this problem report WA's when they used a recursive function to fill the table with a color...

Best regards,
Sebasti

[Sebasti]

i forget to say too that in the commands L, H and K, x1 may be greater than x2 and y1 greater than y2.

bye

[danielrocha]

I got a lot (about 122933483) of WAs before getting AC in this problem. My advise for those who are going crazy is very simple: before freakin out with the "fill" function, make sure ALL the other functions (H, L, V, K) are correct.

I kept receiving WAs, then read here in the board that the judge "would not accept" a recursive filling function. Spent about 1h remaking the function, and then.. Still WA! Later I found out that the problem was in the K function (i know, stupid mistake, i hope it doesnt happen to you guys). When I got AC, I submited with my old recursive function and.. AC again (this time, even faster!)...

So, if you are getting WA, dont freak out and remake your "fill"... Check all you other functions first! Then, if they are all correct, you can go crazy..

Excuse my really bad english,

------

[]'s
Daniel "Nazario" Rocha
Computer Science Student
UFRN - Brasil

[zilnus]

I'm sorry. My English is bad. Anyone can defined this statement to me

Any other pixel which is the same color as pixel(X,Y) and shares a common side with any pixel in R also belongs to this region.

I translate this to C
[cpp]
case 'F' : sscanf (input,"%c %d %d %c",&CC,&X1,&Y1,&color);
CC = pixel[Y1-1][X1-1];
for (i=0;i<N;i++) {
for (j=0;j<M;j++) {
if (pixel[j] == CC) pixel[j] = color;
}
}

break;
[/cpp]
Is not simple like that, is it? I got WA.
Thanx everyone

[titid_gede]

no, it is not like that. it is like flood fill. consider this image:

Code: Select all

aaabbbc
accbbac
baccccb
bacabbb

we need to flood fill the grid 2,3 with newcolor = d
then the image should be :

Code: Select all

aaabbbc
addbbac
baddddb
badabbb

hope this helps.

[zilnus]

Thanx, now I understand. I use recursive, but it is SIGSEV. Is there anyone who can find bug in my source code.
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <string.h>

void tukar(int *a,int *b);
void floodfill(char x[300][300],int X,int Y,char color,char color2,int M,int N);

int main()
{
char pixel[300][300];
char input[35];
char file[100];
char CC,color;
int i,j,k,M,N,X1,X2,Y1,Y2;

while (cin.getline(input,35))
{
if (input[0] == 'X') break;
switch(input[0]) {
case 'I' : sscanf(input,"%c %d %d",&CC,&M,&N);
for (i=0;i<N;i++)
for (j=0;j<M;j++)
pixel[j] = 'O';
break;
case 'C' : for (i=0;i<300;i++)
for (j=0;j<300;j++)
pixel[j] = 'O';
break;
case 'L' : sscanf(input,"%c %d %d %c",&CC,&X1,&Y1,&color);
pixel[Y1-1][X1-1] = color;
break;
case 'V' : sscanf(input,"%c %d %d %d %c",&CC,&X1,&Y1,&Y2,&color);
if (Y1 > Y2) tukar(&Y1,&Y2);
for (i=Y1-1;i<=Y2-1;i++)
pixel[X1-1] = color;
break;
case 'H' : sscanf(input,"%c %d %d %d %c",&CC,&X1,&X2,&Y1,&color);
if (X1 > X2) tukar(&X1,&X2);
for (i=X1-1;i<=X2-1;i++)
pixel[Y1-1] = color;
break;
case 'K' : sscanf(input,"%c %d %d %d %d %c",&CC,&X1,&Y1,&X2,&Y2,&color);
if (X1 > X2) tukar(&X1,&X2);
if (Y1 > Y2) tukar(&Y1,&Y2);
for (i=Y1-1;i<Y2-1;i++)
for (j=X1-1;j<X2-1;j++)
pixel[j] = color;
break;
case 'F' : sscanf (input,"%c %d %d %c",&CC,&X1,&Y1,&color);
floodfill(pixel,X1-1,Y1-1,color,pixel[Y1-1][X1-1],M,N);
break;
case 'S' : sscanf(input,"%c %s",&CC,file);
printf ("%s\n",file);
for (i=0;i<N;i++) {
for (j=0;j<M;j++)
printf ("%c",pixel[j]);
printf ("\n");
}
break;
default : break;
}
}
return 0;
}

void tukar(int *a,int *b)
{
int temp;

temp = *a;
*a = *b;
*b = temp;
}

void floodfill(char x[300][300],int X,int Y,char color,char color2,int M,int N)
{
x[Y][X] = color;

if ( ((X-1) >= 0) && (x[Y][X-1] == color2) )
floodfill(x,X-1,Y,color,color2,M,N);
if ( ((Y-1) >= 0) && (x[Y-1][X] == color2) )
floodfill(x,X,Y-1,color,color2,M,N);
if ( ((X+1) < M) && (x[Y][X+1] == color2) )
floodfill(x,X+1,Y,color,color2,M,N);
if ( ((Y+1) < N)&&(x[Y+1][X] == color2) )
floodfill(x,X,Y+1,color,color2,M,N);

}[/cpp]

I spent hours to find bug. But i am sure there is no invalid reference address.Please help me. Thanx[/c]

[bugzpodder]

I couldnt figure out whats wrong with this. I've switched my fill to BFS instead of DFS (because some ppl said previously that recursive fills would result in error) but still WA. all the commands seem to work perfectly. please help.

note, buggy code due to x2<x, y2<y

[cpp]
//10267 Graphical Editor
#include<iostream>
#include<string>
#include<queue>

using namespace std;
char arr[255][255];
string validcmd="ICLVHKFSX";
char cmd;

void BFS(int x,int y, char org, char c){
queue<pair<int,int> > Q;
pair<int,int> crd;
crd.first=x;
crd.second=y;
Q.push(crd);
while(!Q.empty()) {
crd=Q.front();
Q.pop();
if (arr[crd.first][crd.second]==org){
arr[crd.first][crd.second]=c;
crd.first--; Q.push(crd);
crd.first+=2; Q.push(crd);
crd.first--; crd.second--; Q.push(crd);
crd.second+=2; Q.push(crd);
}
}
}

int main(){
int M,N,i,j,x,y,x2,y2;
char c;
memset(arr,'O',sizeof(arr));
while (1){
for (i=0;i<9;i++) if (cin.peek()==validcmd) break;
cin>>cmd;
if (i==9 || (cin.peek()!=' ' && cin.peek()!='\n')) {
while(cin.peek()!='\n')
cin.ignore();
cmd='-';
}
switch (cmd){
case 'I': cin>>M>>N;
case 'C':
memset(arr,'O',sizeof(arr));
for (i=0;i<=M+1;i++) arr[0]=arr[N+1]='.';
for (i=0;i<=N+1;i++) arr[0]=arr[M+1]='.';
break;
case 'L': cin>>x>>y>>c; arr[x][y]=c; break;
case 'V': cin>>x>>y>>y2>>c;
for (i=y;i<=y2;i++) arr[x]=c;
break;
case 'H': cin>>x>>x2>>y>>c;
for (i=x;i<=x2;i++) arr[y]=c;
break;
case 'K': cin>>x>>y>>x2>>y2>>c;
for (i=x;i<=x2;i++)
for (j=y;j<=y2;j++)
arr[j]=c;
break;
case 'F': cin>>x>>y>>c;
if (c!=arr[x][y]) BFS(x,y,arr[x][y],c);
break;
case 'S': cin.ignore();
while(cin.peek()!='\n') {
cout<<(char)cin.peek();
cin.ignore();
}
cout<<endl;
for (j=1;j<=N;j++){
for (i=1;i<=M;i++)
cout<<arr[j];
cout<<endl;
}
break;
default: break;
}
if (cmd=='X') break;
cin.ignore();
}

return 0;
}
[/cpp]

[BiK]

I spent really a lot of time to a problem that after all doesn't deserve that much time. I got so many WA and I couldn't actually find any problem with my program. Then I wrote my flood function iteratively and instantly got Accepted. However I still don't know what is the problem with the recursive function. I'd be glad if anybody tells me.

My recursive flood function:
[cpp]
void fillRegion(int x, int y, char regionColor, char ch) {
visited[x][y] = true;
bitmap[x][y] = ch;
if (x-1 > 0 && bitmap[x-1][y] == regionColor && !visited[x-1][y])
fillRegion(x-1, y, regionColor, ch);
if (y-1 > 0 && bitmap[x][y-1] == regionColor && !visited[x][y-1])
fillRegion(x, y-1, regionColor, ch);
if (y+1 <= m && bitmap[x][y+1] == regionColor && !visited[x][y+1])
fillRegion(x, y+1, regionColor, ch);
if (x+1 <= n && bitmap[x+1][y] == regionColor && !visited[x+1][y])
fillRegion(x+1, y, regionColor, ch);
}[/cpp]

[danielrocha]

Your recursive function appears to be ok. Could you please send your complete program? The problem may be elsewhere...

[BiK]

Here goes the whole program:

[cpp]
#include <iostream.h>
#include <fstream.h>

#define min(x, y) (x < y ? (x) : (y))
#define max(x, y) (x > y ? (x) : (y))
#define inBoard(x, y) 0 < x && x <= n && 0 < y && y <= m

const int TABLE_SIZE = 250;
const int BUFFER_SIZE = 100;

int m = 0, n = 0;
char bitmap[TABLE_SIZE+1][TABLE_SIZE+1];
bool visited[TABLE_SIZE+1][TABLE_SIZE+1];

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

void anullTable() {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
bitmap[j] = 'O';
}

void afalseTable() {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
visited[j] = false;
}

void drawRect(int x, int y, int z, int t, char ch) {
for(int i = x; i <= z; i++)
for(int j = y; j <= t; j++)
bitmap[j] = ch;
}

void fillRegion(int x, int y, char regionColor, char ch) {
visited[x][y] = true;
bitmap[x][y] = ch;
if (x-1 > 0 && bitmap[x-1][y] == regionColor && !visited[x-1][y])
fillRegion(x-1, y, regionColor, ch);
if (y-1 > 0 && bitmap[x][y-1] == regionColor && !visited[x][y-1])
fillRegion(x, y-1, regionColor, ch);
if (y+1 <= m && bitmap[x][y+1] == regionColor && !visited[x][y+1])
fillRegion(x, y+1, regionColor, ch);
if (x+1 <= n && bitmap[x+1][y] == regionColor && !visited[x+1][y])
fillRegion(x+1, y, regionColor, ch);
}

void fillRegion2(int x, int y, char regionColor, char ch) {
int queue[TABLE_SIZE * TABLE_SIZE + 1][2];
queue[0][0] = x;
queue[0][1] = y;
visited[x][y] = true;
int i = 0, j = 1;
while(i < j) {
i++;
bitmap[queue[i-1][0]][queue[i-1][1]] = ch;

int nX = queue[i-1][0] - 1;
int nY = queue[i-1][1];
if (inBoard(nX, nY) && bitmap[nX][nY] == regionColor && !visited[nX][nY]) {
visited[nX][nY] = true;
queue[j][0] = nX;
queue[j++][1] = nY;
}
nX = queue[i-1][0];
nY = queue[i-1][1] + 1;
if (inBoard(nX, nY) && bitmap[nX][nY] == regionColor && !visited[nX][nY]) {
visited[nX][nY] = true;
queue[j][0] = nX;
queue[j++][1] = nY;
}
nX = queue[i-1][0] + 1;
nY = queue[i-1][1];
if (inBoard(nX, nY) && bitmap[nX][nY] == regionColor && !visited[nX][nY]) {
visited[nX][nY] = true;
queue[j][0] = nX;
queue[j++][1] = nY;
}
nX = queue[i-1][0];
nY = queue[i-1][1] - 1;
if (inBoard(nX, nY) && bitmap[nX][nY] == regionColor && !visited[nX][nY]) {
visited[nX][nY] = true;
queue[j][0] = nX;
queue[j++][1] = nY;
}
}
}

void main() {


char buffer[BUFFER_SIZE];
while(true) {
char ch;
cin >> ch;
if (ch != 'I' && ch != 'C' && ch != 'L' && ch != 'V' && ch != 'H' &&
ch != 'K' && ch != 'F' && ch != 'S' && ch != 'X')
{
cin.getline(buffer, BUFFER_SIZE);
continue;
}
if (ch == 'X')
break;
int x, y, z, t;
switch(ch) {
case 'I': cin >> m >> n;
anullTable();
break;
case 'C': anullTable();
break;
case 'L': cin >> x >> y >> ch;
bitmap[y][x] = ch;
break;
case 'V': cin >> x >> y >> z >> ch;
for(int i = min(y, z); i <= max(y, z); i++)
bitmap[x] = ch;
break;
case 'H': cin >> x >> y >> z >> ch;
for(int i = min(x, y); i <= max(x, y); i++)
bitmap[z] = ch;
break;
case 'K': cin >> x >> y >> z >> t >> ch;
drawRect(y, x, t, z, ch);
break;
case 'F': cin >> x >> y >> ch;
afalseTable();
fillRegion2(y, x, bitmap[y][x], ch);
break;
case 'S': cin >> buffer;
cout << buffer << endl;
printTable();
break;
}
}
}[/cpp]