Page 8 of 13
General Notes
Posted: Thu Jul 12, 2007 1:08 am
by 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.
Posted: Wed Aug 01, 2007 6:09 pm
by 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]
Posted: Mon Aug 06, 2007 11:06 pm
by 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.
Posted: Mon Aug 06, 2007 11:10 pm
by 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.
Posted: Thu Aug 30, 2007 7:48 pm
by 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.
I've tried so many times on this one
Posted: Wed Nov 28, 2007 2:52 am
by 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;
}
For those of you struggling with WA...
Posted: Sat Dec 01, 2007 1:51 am
by 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.
Posted: Sun Mar 02, 2008 6:23 pm
by 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)
Posted: Fri Mar 07, 2008 7:05 pm
by 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
Posted: Fri Mar 07, 2008 7:07 pm
by 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.
Posted: Sun Mar 09, 2008 2:51 am
by 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';
}
}
Re: 10267 - Graphical Editor
Posted: Tue Jul 01, 2008 1:47 am
by 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:
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
Re: 10267 - Graphical Editor
Posted: Sat Jul 19, 2008 3:56 pm
by 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;
}
Re: 10267 - Graphical Editor
Posted: Sat Sep 06, 2008 2:42 pm
by rabiee
Hi all,
My code takes forever(TLE) on getline statement in the judge, but works fine on my machine.
Can anyone help?
Re: 10267 - Graphical Editor
Posted: Sat Oct 04, 2008 12:15 am
by 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
