785 - Grid Colouring

[broderic]

Do i have to check if a marking is inside a closed zone before
i attempt to fill it?

As it is, i'm not doing that and my submission keeps getting rejected.

Thanks
Broderick

[wyvmak]

i think yes, and you've to check that only one type of mark will be "painted", ie. a zone with 'A' and 'B' will not be filled

[sjn]

my code works perfectly before Ctrl+Z (that is eof)
thx in advance

[sjn]

Who can tell me how to do with the end of output?

[cytse]

I don't think so...
I haven't checked for it, and still got AC.

[Jalal]

Lets take a int n if u want to take it as a input with EOF
then:
while(sccanf("%d", &n)!=EOF)
{
--------
}

[gustu]

I assume, there is a tricky input for that problem. Me and a friend of me, we are trying to solve that problem and have both correct programs. At least, we think so. There is my code, in case you want to read JAVA.

import java.io.*;
import java.util.*;
import java.lang.*;

class Main
{
//int anzmazes;
char [] [] maze;
//int startx = 0, starty = 0;
Vector markX;
Vector markY;
Vector marker;
String trenner;
char mauer;
//int mazelange;

static String ReadLn (int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
//String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}

void Begin()
{
String in;
boolean anfang;
//anzmazes = Integer.parseInt(in);
while ( true ) { //f

[bobi1978]

1) You DON'T have to check for markers that are not in a closed zone.
2) You DON'T have to check if there are diferent markers in one zone.
At least I DIDN'T and got ACC.

[schang]

hi, i always get a runtime error:

Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

i really don't know why, my sample inputs work great! take a look at my code, perhaps you know the reason...

[cpp]#include <iostream>
using namespace std;

#define BUFSIZE 32768

char buf[BUFSIZE]; //inbuffer
char obuf[BUFSIZE]; //outbuffer
char *bufp; //index inbuffer
char *bufend;
int obufp; //index outbuffer
int iseof; //reached eof

char A[35][85]; //grid
int sp[35] = {0}; //coloums per line
int z; //lines per grid
int posi, posj;
char guard;

void findguard(){
for(int i = 0; i < z; i++){
for(int j = 0; i < sp; j++){
if(A[j] == '\n')
break;
if(A[j] != ' '){
guard = A[j];
posi=i;
posj=j;
return;
}
}
}
}

void fillfields(char slave, int filli, int fillj){
if(A[filli-1][fillj]!= slave && A[filli-1][fillj]!= guard){
A[filli-1][fillj]=slave;
fillfields(slave, filli-1, fillj);
}
if(A[filli][fillj-1]!= slave && A[filli][fillj-1]!= guard){
A[filli][fillj-1]=slave;
fillfields(slave, filli, fillj-1);
}
if(A[filli+1][fillj]!= slave && A[filli+1][fillj]!= guard){
A[filli+1][fillj]=slave;
fillfields(slave, filli+1, fillj);
}
if(A[filli][fillj+1]!= slave && A[filli][fillj+1]!= guard){
A[filli][fillj+1]=slave;
posj++;
fillfields(slave, filli, fillj+1);
}
return;
}

void makerest(){
/*cout << "posi " << posi << endl;*/
for(int j = posj; j < sp[posi]; j++){
if(A[posi][j]==guard || A[posi][j]==' ' || A[posi][j] == '\n' || A[posi][j] == '_') continue;
else{
fillfields(A[posi][j], posi, j);
}
}
return;
}

void findslaves(){
for(int i = posi; i < z; i++){
for(int j = 0; j < sp; j++){
if(A[j]==guard || A[j]==' ' || A[j] == '\n' || A[j] == '_') continue;
else{
posi = i;
posj = j;
fillfields(A[j], posi, posj);
makerest();
break;
}
}
}
return;
}

void bufrefill()
{
int rest = bufend-bufp;
memcpy(buf,bufp,rest);
cin.read(buf+rest,sizeof(buf)-rest);
bufp=buf;
bufend = buf+rest+cin.gcount();
iseof = cin.eof();
return;
}


int main()
{
char check = 0;
int temp = 0;

cin.read(buf,sizeof(buf));
bufp = buf;
bufend = buf+cin.gcount();
iseof = cin.eof();
obufp = 0;

while(true)
{
temp++;

if (bufend-bufp < 35*85 && !iseof) /*check buffer contents*/
{
bufrefill();
}
z=0;

for(int i=0; i<35; i++)
{
sp[i] = 0; /*reset coloums*/
for(int j=0; j<85; j++)
{
A[i][j] = *bufp; /*fill grid*/
sp[i]++; /*coloums for this line*/
bufp++;
if(A[i][j] == '\n' || *bufp == 0) /*EOF or end of grid*/
{
check = A[i][j-1];
break;
}

}
z++;
if(check == '_') /*end of grid*/
break;
}


findguard();
findslaves();

if(obufp > BUFSIZE - (35*85)) /*write outbuffer*/
{
cout.write(obuf, obufp);
obufp = 0;
}

for(int i=0; i<z; i++)
{
for(int j=0; j<sp[i]; j++)
{
obuf[obufp] = A[i][j]; /*fill outbuffer*/
obufp++;
}
}
if(*bufp == 0) /*terminating zero*/
break;
}
if(obufp > 0) /*write outbuffer*/
cout.write(obuf, obufp);
return 0;
}[/cpp]

thanks for any help!

[A1]

I am getting wrong answer in this 785(Grid Colouring) problem

for input:

Code: Select all

\n
  XXXXXXXXXXXXXXXXXXXX
  X      X           X
  X # #  XXXXXXXX /  X
  X             X    X
  XXXXXXXXXXXXXXXXXXXX
_____________________________
\n
   XXXXXXXXXXXX       XXXXXX
  X       #   XXX  XXX   X X
  X  XX         X  X     X X
 X  X  X  XXXXXXX  XXXXXXX
 X   XX   X
  X       X  XXXX  XXXXXXXX
   XX     XXXX  X  X  /   X
    X           X  X    / X
    XXXXXXXXXXXXX  XXXXXXXX
_____________________________
\n

My program output is:

Code: Select all

\n
  XXXXXXXXXXXXXXXXXXXX
  X######X///////////X
  X######XXXXXXXX////X
  X#############X////X
  XXXXXXXXXXXXXXXXXXXX
_____________________________
\n
   XXXXXXXXXXXX       XXXXXX
  X###########XXX  XXX   X X
  X##XX#########X  X     X X
 X##X  X##XXXXXXX  XXXXXXX
 X###XX###X
  X#######X  XXXX  XXXXXXXX
   XX#####XXXX##X  X//////X
    X###########X  X//////X
    XXXXXXXXXXXXX  XXXXXXXX
_____________________________
\n

\n = blank line

Is there any wrong in my output? please give some more input output.

[A1]

Ok! I found my problem and got AC

Thanks

[yiuyuho]

just cursious, what was your problem?

[yiuyuho]

note that the line of underscores is not part of the grid, thus is not restricted to 80 characters max in that line.

[A1]

problem was :
first I assume that there will be only
# and / characters for fill but there could be any character excluding

Code: Select all

X and _ 

Thanks to the previous posts

[poweron21c]

Code: Select all

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
char map[100][100];
int m,n;
void dfs(int x,int y,char c)
{
        map[x][y] = c;
        if(x-1 >=0 && map[x-1][y] !='X' && map[x-1][y] !=c)
                dfs(x-1,y,c);
        if(y-1>=0 && map[x][y-1] !='X' && map[x][y-1] !=c)
                dfs(x,y-1,c);
        if(x<=n-2 && map[x+1][y] != 'X' && map[x+1][y] !=c)
                dfs(x+1,y,c);
        if(y<=m-1 && map[x][y+1] != 'X' && map[x][y+1] !=c)
                dfs(x,y+1,c);
}


int main()
{
        int i,j;
        memset(map,0,sizeof(map));
        while(gets(map[0])){
                m = 30;
                n=0;
                while(map[n][0] !='_')
                        cin.getline(map[++n], 100);

                for(i=0;i<n;i++)
                        for(j=0;j<m;j++)
                                if(map[i][j] != ' ' && map[i][j] !='X' && map[i][j] !='\n' && map[i][j] !='\0'  && map[i][j] !='\t')
                                        dfs(i,j,map[i][j]);

                for(i=0;i<=n;i++)
                        cout <<map[i]<<endl;

                n=0;

                memset(map,0,sizeof(map));
        }
        return 0;
}

Why is my code WA?[/code]