Page 1 of 2
785 - Grid Colouring
Posted: Thu Jun 06, 2002 4:37 am
by 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
Posted: Sun Jun 16, 2002 4:16 pm
by 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
785 Runtime Error (SIGSEGV) why?
Posted: Sun Oct 06, 2002 10:03 pm
by sjn
my code works perfectly before Ctrl+Z (that is eof)
thx in advance
Posted: Sun Oct 06, 2002 10:07 pm
by sjn
Who can tell me how to do with the end of output?
Posted: Sat Oct 12, 2002 7:22 pm
by cytse
I don't think so...
I haven't checked for it, and still got AC.
Posted: Sun Jan 05, 2003 10:45 pm
by Jalal
Lets take a int n if u want to take it as a input with EOF
then:
while(sccanf("%d", &n)!=EOF)
{
--------
}
785
Posted: Wed Apr 23, 2003 3:58 pm
by 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
Posted: Fri Aug 08, 2003 8:28 am
by 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.
Posted: Mon May 31, 2004 2:25 pm
by schang
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!
785(Grid Colouring) WA
Posted: Mon Oct 11, 2004 7:43 am
by 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.
Posted: Tue Oct 12, 2004 9:46 am
by A1
Ok! I found my problem and got AC
Thanks
Posted: Sat Nov 06, 2004 6:56 am
by yiuyuho
just cursious, what was your problem?
Posted: Sat Nov 06, 2004 7:12 am
by yiuyuho
note that the line of underscores is not part of the grid, thus is not restricted to 80 characters max in that line.
Posted: Sat Nov 06, 2004 7:59 am
by A1
problem was :
first I assume that there will be only
# and / characters for fill but there could be any character excluding
Thanks to the previous posts
785
Posted: Tue Aug 02, 2005 7:54 am
by 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]