785 - Grid Colouring
Moderator: Board moderators
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
i attempt to fill it?
As it is, i'm not doing that and my submission keeps getting rejected.
Thanks
Broderick
785 Runtime Error (SIGSEGV) why?
my code works perfectly before Ctrl+Z (that is eof)
thx in advance![:-?](./images/smilies/icon_confused.gif)
thx in advance
![:-?](./images/smilies/icon_confused.gif)
Last edited by sjn on Mon Feb 02, 2004 5:38 pm, edited 1 time in total.
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)
{
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
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
hi, i always get a runtime error:
[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!
i really don't know why, my sample inputs work great! take a look at my code, perhaps you know the reason...Judge wrote:Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
[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
I am getting wrong answer in this 785(Grid Colouring) problem
for input:
My program output is:
\n = blank line
Is there any wrong in my output? please give some more input output.
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
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
Is there any wrong in my output? please give some more input output.
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 ![:)](./images/smilies/icon_smile.gif)
first I assume that there will be only
# and / characters for fill but there could be any character excluding
Code: Select all
X and _
![:)](./images/smilies/icon_smile.gif)
-
- 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;
}