785 - Grid Colouring

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

785 - Grid Colouring

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
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:

785 Runtime Error (SIGSEGV) why?

my code works perfectly before Ctrl+Z (that is eof)
Last edited by sjn on Mon Feb 02, 2004 5:38 pm, edited 1 time in total.

sjn
Learning poster
Posts: 73
Joined: Mon Apr 08, 2002 8:22 am
Contact:
Who can tell me how to do with the end of output?

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
I don't think so...
I haven't checked for it, and still got AC.

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
Lets take a int n if u want to take it as a input with EOF
then:
while(sccanf("%d", &n)!=EOF)
{
--------
}

gustu
New poster
Posts: 1
Joined: Wed Apr 23, 2003 3:51 pm

785

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)
{
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
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Contact:
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
New poster
Posts: 2
Joined: Sat Apr 24, 2004 11:25 pm
hi, i always get a runtime error:
Judge wrote: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);
bufp=buf;
bufend = buf+rest+cin.gcount();
iseof = cin.eof();
return;
}

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

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
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

785(Grid Colouring) WA

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
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Ok! I found my problem and got AC

Thanks

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
just cursious, what was your problem?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
note that the line of underscores is not part of the grid, thus is not restricted to 80 characters max in that line.

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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
New poster
Posts: 1
Joined: Tue Aug 02, 2005 7:42 am

785

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]