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
Location: Canada

785 - Grid Colouring

Post by broderic » Thu Jun 06, 2002 4:37 am

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

Post by wyvmak » Sun Jun 16, 2002 4:16 pm

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?

Post by sjn » Sun Oct 06, 2002 10:03 pm

my code works perfectly before Ctrl+Z (that is eof)
thx in advance :-?
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:

Post by sjn » Sun Oct 06, 2002 10:07 pm

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

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse » Sat Oct 12, 2002 7:22 pm

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
Location: BANGLADESH
Contact:

Post by Jalal » Sun Jan 05, 2003 10:45 pm

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

Post by gustu » Wed Apr 23, 2003 3:58 pm

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
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post by bobi1978 » Fri Aug 08, 2003 8:28 am

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

Post by schang » Mon May 31, 2004 2: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);
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!

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

785(Grid Colouring) WA

Post by A1 » Mon Oct 11, 2004 7:43 am

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.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Tue Oct 12, 2004 9:46 am

Ok! I found my problem and got AC :D

Thanks

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Nov 06, 2004 6:56 am

just cursious, what was your problem?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sat Nov 06, 2004 7:12 am

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Sat Nov 06, 2004 7:59 am

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

Post by poweron21c » Tue Aug 02, 2005 7:54 am

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]

Post Reply

Return to “Volume 7 (700-799)”