782 - Contour Painting

kmhasan · Post by **kmhasan** » Wed Mar 19, 2003 8:48 pm

I'm also getting plenty of WAs

Could you people who got AC help me with the output for the following input:

2
XXXX
A AA
AA*A
XXXX
_____
  XXXXXXXXXX
  X        X
  X  XXXX  X
  X X *  X X
  XXXXXXXXXX
__

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Mar 19, 2003 9:19 pm

The output is:

Code: Select all

XXXX 
A AA 
AA#A 
XXXX 
_____ 
  XXXXXXXXXX 
  X        X 
  X  XXXX  X 
  X X####X X 
  XXXXXXXXXX 
__

The input contains at least one test case with no trailing spaces, but you need to extend a line to the right if you should paint the exterior, so it is possible that the output line contains 81 characters.

kmhasan · Post by **kmhasan** » Wed Mar 19, 2003 11:03 pm

Thanks a lot, Adrian. Filling up the null characters with spaces, in a num_of_rows x 85 size board and thereby extending the original one to the right actually worked. I got AC.

I thought I had that case where there's no trailing space, covered. Don't actually know what could be a case where filling up with spaces might result in something different.

There certainly can't be a case where there are null characters in between some characters in a line, right? Because, the last modification I did takes care of this seemingly impossible situation.

Anyway, thanks again.

angga888 · Post by **angga888** » Thu Mar 20, 2003 3:50 pm

Dear Saiqbal,
About 3 spaces at the end of the second line, it's my mistake, sorry!

There should not be any trailing spaces after the end of grid.
But that will cause only P.E. not W.A. though...

Try to add another spaces at the end of a grid when you read from input. But don't print that spaces in the output.

Good Luck !

raysa · Post by **raysa** » Thu Mar 20, 2003 4:17 pm

Fixed, but still Still WA <0.361 sec>...
After expanding the NULL with white space, do we have to return it to it's original form before printing?
So, what's the output for:

Code: Select all

______
bbbbbb
b
b
b
______
bbbbbb
b
b*
b
______

with b represents white space? <Please answer also with b-represented white space>
Btw, can tab <'\t'> be a valid input to handle?

Thank's,
Raysa

angga888 · Post by **angga888** » Fri Mar 21, 2003 12:49 pm

If you don't return it to it's original form before printing, you'll get P.E.

My ACC solution gives no output for your input, just a blank grid with underscores.
Btw, I don't care about tab <'\t'>.

Good luck !

nagary · Post by **nagary** » Sun Jul 20, 2003 8:33 pm

I have encountered a runtime error (invalid memory reference) when I submit my code to online judge for 20 times

.

It works well with grid with 30 rows and 80 columns.

I can't dig out the bug.
Would anybody help me ? thank you

Code: Select all

[c]
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MAX_ROW 31
#define MAX_COL 81

/* start of data structures used in BSP */

struct point{

	int row ;
	int col ;

} ;

typedef struct point Point ;

Point *queue ;
int sizeOfQueue ;

/* the max nos of columns in the output line is MAX_COL (81) */

int visited[MAX_ROW][MAX_COL] ;

/* end of data structures used in BSP */

char grid[MAX_ROW][MAX_COL+1] ;

void printContour(int lineNum){

	int i ;
	int col ;
	int finishRemovingTrailingSpaces ; 

	for(i=0 ; i<=lineNum ; i++){

		finishRemovingTrailingSpaces = 0 ;
		col = MAX_COL-1 ;
		/* set the trailing space to a null character */
		
		do{
		
			if(grid[i][col]==' '){
				grid[i][col] = '\0' ;
			}else{
				finishRemovingTrailingSpaces = 1 ;
			}

			col-- ;

			if(col<0){
				finishRemovingTrailingSpaces = 1 ;
			}

		}while(!finishRemovingTrailingSpaces) ;
		
		printf("%s\n",grid[i]) ;
	}
}

Point extractQueue(){

	int i ;
	Point head ;

	head = queue[0] ;

	for(i=1 ; i<sizeOfQueue ; i++){
		queue[i-1] = queue[i] ;		
	}

	sizeOfQueue-- ;
	queue = (Point*)realloc(queue,sizeof(Point)*sizeOfQueue) ;

	return head ;

}	/* extractQueue() */

void addQueue(int row,int col){

	Point newPoint ;

	newPoint.row = row ;
	newPoint.col = col ;

	sizeOfQueue++ ;
	queue = (Point*)realloc(queue,sizeof(Point)*sizeOfQueue) ;
	queue[sizeOfQueue-1] = newPoint ; 

	visited[row][col] = 1 ;

}	/* addQueue() */

int outOfBound(int row,int col,int terminatingLine){

	if(row<0 || row>=terminatingLine)	/* [0..terminatingLine-1] */
		return 1 ;
	else if(col<0 || col>=MAX_COL)	/* [0..MAX_COL-1] */
		return 1 ;
	else
		return 0 ;

}	/* outOfBound() */

void paintByBFS(int starRow,int starCol,int terminatingLine){

	Point point ;
	int row ;
	int col ;

	sizeOfQueue = 0 ;
	queue = (Point*)malloc(sizeof(Point)) ;

	/* add the source to the queue */
	addQueue(starRow,starCol) ;
	/* turn the star into space */
	grid[starRow][starCol] = ' ' ;

	while(sizeOfQueue!=0){
	
		point = extractQueue() ;
		row = point.row ;
		col = point.col ;

		/* Go through all vertical and horizontal neighbours of current point */
		/* not out of bound and not visited */

		if(!outOfBound(row,col+1,terminatingLine) && !visited[row][col+1]){
			if(grid[row][col+1]!=' '){
				grid[row][col] = '#' ;
			}else{
				addQueue(row,col+1) ;				
			}
		}

		if(!outOfBound(row,col-1,terminatingLine) && !visited[row][col-1]){
			if(grid[row][col-1]!=' '){
				grid[row][col] = '#' ;
			}else{
				addQueue(row,col-1) ;				
			}
		}

		if(!outOfBound(row+1,col,terminatingLine) && !visited[row+1][col]){
			if(grid[row+1][col]!=' '){
				grid[row][col] = '#' ;
			}else{
				addQueue(row+1,col) ;				
			}		
		}

		if(!outOfBound(row-1,col,terminatingLine) && !visited[row-1][col]){
			if(grid[row-1][col]!=' '){
				grid[row][col] = '#' ;
			}else{
				addQueue(row-1,col) ;				
			}		
		}
	}

}

void contourPainting(int lineNum,int starRow,int starCol){

	/*
	printf("the coordinate of the star is (%d,%d)\n",starRow,starCol) ;*/
	
	/* paint by BFS*/
	paintByBFS(starRow,starCol,lineNum) ;

	/* print out the already coloured grid */
	printContour(lineNum) ;

}

void resetGrid(){

	int i,j ;

	for(i=0 ; i<MAX_ROW ; i++){
		for(j=0 ; j<MAX_COL ; j++){
			/* turn characters at each point to space */
			grid[i][j] = ' ' ;
			visited[i][j] = 0 ;
		}
		/* set null character at the end of each line */
		grid[i][MAX_COL] = '\0' ;
	}

}

int main(int args,char *argv[]){

	int i ;
	int starRow ;
	int starCol ;
	int lineNum ;
	const int numOfGrids ;
	int numOfSeparationLine ;
	char line[80] ;

	lineNum = 0 ;
	numOfSeparationLine = 0 ;

	gets(line) ;
	sscanf(line,"%d",&numOfGrids) ;

	resetGrid() ;

	while(1){
	
		gets(grid[lineNum]) ;

		/* append the space to the end of line until 81th column */
		/* Therefore each line will end at the 81th column regardless 
		   of the length of input lines */
		for(i=strlen(grid[lineNum]) ; i<MAX_COL ; i++){
			grid[lineNum][i] = ' ' ;
		}
		
		grid[lineNum][MAX_COL] = '\0' ;

		if(grid[lineNum][0]=='_')
		{
			contourPainting(lineNum,starRow,starCol) ;

			lineNum = 0 ;
			numOfSeparationLine++ ;	
			
			/* encounter the last grid */
			if(numOfGrids==numOfSeparationLine)
			{
				break ;
			}
			else
			{
				/* reset the grid before input the next grid */
				resetGrid() ;
			}

		}
		else
		{
			/* find the star after feeding one line */
			for(i=0 ; i < (signed)strlen(grid[lineNum]) ; i++){
				if(grid[lineNum][i]=='*'){
					starRow = lineNum ;
					starCol = i ;
				}
			}

			lineNum++ ;
		}


	}	/* while(1) */

	return 0 ;

}
[/c]

nagary · Post by **nagary** » Mon Jul 21, 2003 10:41 am

I found that the problem is due to this code fragment in main() method

Code: Select all

[c]
      for(i=strlen(grid[lineNum]) ; i<MAX_COL ; i++){ 
         grid[lineNum][i] = ' ' ; 
      } 
[/c]

But I still don't know how it causes invalid memory reference[/code]

watershed · Post by **watershed** » Mon Jan 24, 2005 4:55 pm

I need your help if you got AC.

Code: Select all

#include<stdio.h>
#include<string.h>
char map[50][100];
int line,maxlen; // maxlen is the most long length
int ch_x,ch_y;   // coordinate of asterisk
void input()
{
  line = maxlen = 0;
  while( gets(map[line]) ) {
        if( !strcmp(map[line],"__________") ) break;
        int len = strlen(map[line]);
        if( maxlen < len ) maxlen = len;
        ++line;
  }
}
int FindAsterisk()
{
  for(int i=0; i<line; ++i) {
        int len = strlen(map[i]);
        for(int j=0; j<len; ++j)
                if( map[i][j] == '*' ) {
                        ch_x = j;
                        ch_y = i;
                        map[i][j] = ' ';
                        return 0;
                }
  }
}
int FindAround(int x, int y)
{
  if( map[y][x] == ' ' || map[y][x] == '#' || map[y][x] == '@' ||
      map[y][x] == '\0' ) return 0;
  return 1;
}
int FindAround1(int x, int y)
{
  if( map[y][x] == ' ' || map[y][x] == '\0' ) return 1;
  return 0;
}
void recursion(int x, int y)
{
  map[y][x] = '@';
  if( y<line-1 && FindAround(x,y+1) ) map[y][x] = '#';
  if( y        && FindAround(x,y-1) ) map[y][x] = '#';
  if( x<maxlen && FindAround(x+1,y) ) map[y][x] = '#';
  if( x        && FindAround(x-1,y) ) map[y][x] = '#';

  if( y<line-1 && FindAround1(x,y+1) ) recursion(x,y+1);
  if( y        && FindAround1(x,y-1) ) recursion(x,y-1);
  if( x<maxlen && FindAround1(x+1,y) ) recursion(x+1,y);
  if( x        && FindAround1(x-1,y) ) recursion(x-1,y);
}
void output()
{
  for(int i=0; i<=line; ++i) {
        int len = strlen(map[i]);
        for(int j=0; j<len; ++j) {
                if( map[i][j] == '@' ) printf(" ");
                else printf("%c",map[i][j]);
                map[i][j] = '\0';
        }
        printf("\n");
  }
}
main()
{
  int n;
  scanf("%d%c",&n,&map[0][0]);
  for(; n>0; --n) {
        input();
        FindAsterisk();
        recursion(ch_x,ch_y); // fill '#'
        output();
  }
}

thanks for your help

watershed · Post by **watershed** » Mon Jan 24, 2005 4:55 pm

I need your help if you got AC.

Code: Select all

#include<stdio.h>
#include<string.h>
char map[50][100];
int line,maxlen; // maxlen is the most long length
int ch_x,ch_y;   // coordinate of asterisk
void input()
{
  line = maxlen = 0;
  while( gets(map[line]) ) {
        if( !strcmp(map[line],"__________") ) break;
        int len = strlen(map[line]);
        if( maxlen < len ) maxlen = len;
        ++line;
  }
}
int FindAsterisk()
{
  for(int i=0; i<line; ++i) {
        int len = strlen(map[i]);
        for(int j=0; j<len; ++j)
                if( map[i][j] == '*' ) {
                        ch_x = j;
                        ch_y = i;
                        map[i][j] = ' ';
                        return 0;
                }
  }
}
int FindAround(int x, int y)
{
  if( map[y][x] == ' ' || map[y][x] == '#' || map[y][x] == '@' ||
      map[y][x] == '\0' ) return 0;
  return 1;
}
int FindAround1(int x, int y)
{
  if( map[y][x] == ' ' || map[y][x] == '\0' ) return 1;
  return 0;
}
void recursion(int x, int y)
{
  map[y][x] = '@';
  if( y<line-1 && FindAround(x,y+1) ) map[y][x] = '#';
  if( y        && FindAround(x,y-1) ) map[y][x] = '#';
  if( x<maxlen && FindAround(x+1,y) ) map[y][x] = '#';
  if( x        && FindAround(x-1,y) ) map[y][x] = '#';

  if( y<line-1 && FindAround1(x,y+1) ) recursion(x,y+1);
  if( y        && FindAround1(x,y-1) ) recursion(x,y-1);
  if( x<maxlen && FindAround1(x+1,y) ) recursion(x+1,y);
  if( x        && FindAround1(x-1,y) ) recursion(x-1,y);
}
void output()
{
  for(int i=0; i<=line; ++i) {
        int len = strlen(map[i]);
        for(int j=0; j<len; ++j) {
                if( map[i][j] == '@' ) printf(" ");
                else printf("%c",map[i][j]);
                map[i][j] = '\0';
        }
        printf("\n");
  }
}
main()
{
  int n;
  scanf("%d%c",&n,&map[0][0]);
  for(; n>0; --n) {
        input();
        FindAsterisk();
        recursion(ch_x,ch_y); // fill '#'
        output();
  }
}

thanks for your help

oulongbin · Post by **oulongbin** » Sat Mar 19, 2005 9:02 am

always get RTE,i do not know why.

Code: Select all

#include <iostream>
using namespace std;
#include <cstring>


char arr[50][100];
bool f[50][100];
int len,tlen;
int k;

void indraw(int i,int j)
{
		if(i-1>=0 && f[i-1][j] && arr[i-1][j]!='X')
		{
			f[i-1][j]=false;
			indraw(i-1,j);
		}

		if(i+1<k && f[i+1][j] && arr[i+1][j]!='X')
		{
			f[i+1][j]=false;
			indraw(i+1,j);
		}

		if(j-1>=0 && f[i][j-1] && arr[i][j-1]!='X')
		{
			f[i][j-1]=false;
			indraw(i,j-1);
		}
	
		if(j+1<len && f[i][j+1] && arr[i][j+1]!='X')
		{
			f[i][j+1]=false;
			indraw(i,j+1);
		}

}

void draw()
{
	int i,j;
	for(i=0;i<k;i++)
	{
		for(j=0;j<len;j++)
		{
			if(!f[i][j])
			{
				if(i-1>=0 && arr[i-1][j]=='X')
				{
					arr[i][j]='#';
				}
				if(i+1<k && arr[i+1][j]=='X')
				{
					arr[i][j]='#';
				}
				if(j-1>=0 && arr[i][j-1]=='X')
				{
					arr[i][j]='#';
				}
				if(j+1<len && arr[i][j+1]=='X')
				{
					arr[i][j]='#';
				}
			}
		}
	}
}

int main() 
{ 
	int n;
	int i,j;
	int x,y;
	cin>>n;
	cin.get();
	while(n--)
	{
		k=0;
		len=0;
		tlen;
		while(cin.getline(arr[k],100))
		{
			if(!strcmp(arr[k],"__________"))
				break;
			tlen=strlen(arr[k]);
			if(tlen>len)
			{
				len=tlen;
			}
			k++;
		}
		len++;
		for(i=0;i<k;i++)
		{
			tlen=strlen(arr[i]);
			if(tlen<len)
			{
				for(j=tlen;j<len;j++)
				{
					arr[i][j]=' ';
				}
				arr[i][j]='\0';
			}
		}
		for(i=0;i<k;i++)
		{
			for(j=0;j<len;j++)
			{
				if(arr[i][j]=='*')
				{
					x=i;
					y=j;
					arr[i][j]=' ';
					break;
				}
			}
			if(j!=len)
				break;
		}
		
		memset(f,true,sizeof(f));
		
		f[x][y]=false;
		indraw(x,y);
		draw();
		
		for(i=0;i<k;i++)
		{
			for(j=len-1;j>=0;j--)
			{
				if(arr[i][j]!=' ')
				{
					arr[i][j+1]='\0';
					break;
				}
			}
			if(j==-1)
			{
				arr[i][0]='\0';
			}
		}
		for(i=0;i<k+1;i++)
		{
			cout<<arr[i]<<endl;
		}
	}
    return 0; 
}

seedman · Post by **seedman** » Fri Oct 28, 2005 11:39 am

what's the correct answer for these tricky input???
could anyone with AC program post these answer? plz~

seedman · Post by **seedman** » Sat Oct 29, 2005 11:29 am

I've got AC now....
I didn't change any algorithm, only change "vector<vector<char> > map" to "char **map, DIM_X, DIM_Y "...............

Is this codeing style problem or gcc bug?

zid_adrenalyns · Post by **zid_adrenalyns** » Thu Aug 23, 2007 3:22 am

angga888 wrote:If you don't return it to it's original form before printing, you'll get P.E.
My ACC solution gives no output for your input, just a blank grid with underscores.
Btw, I don't care about tab <'\t'>.

Good luck !

I don't know if my output mantain de original form of the input

. I get PE for this problem. Somebody helps?
Input

Code: Select all

7

XXXXXXX
X*X
XXXXXXX

__________

       XXXXXXXXXX
      XXXX       XX
      X            X
     X      X      XXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX      *XX
       XXXXXXXXXX

__________

       XXXXXXXXXX
 *    XXXX       XX
      X            X
     X      X      XXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX       XX
       XXXXXXXXXX

__________
XXXXXXXXXXXXX
X       X  *
XXXXXXXXXXXXXXX
____
  XXXXXXXXXX
  X        X
  X  XXXX  X
  X X *  X X
  XXXXXXXXXX
__
       XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
      XXXX       XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
      X                        XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
     X      X      XXXXXXXXXXXXXXXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX      *XX
       XXXXXXXXXX

__________
       XXXXXXXXXX
 *    XXXX       XX
      X            X
     X      X      XXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX       XX
       XXXXXXXXXX
__________

output

Code: Select all

XXXXXXX
X#X
XXXXXXX

__________

       XXXXXXXXXX
      XXXX#######XX
      X###  #    ##X
     X######X#    #XXXXXXX
     XXXXXXXX#     #######XX
     X######X#    #XXXXXXX
      X###  #    ##X
      XXXX#######XX
       XXXXXXXXXX

__________
       ##########
      #XXXXXXXXXX##
     #XXXX       XX#
     #X            X######
    #X      X      XXXXXXX##
    #XXXXXXXX             XX#
    #X      X      XXXXXXX##
     #X            X######
     #XXXX       XX#
      #XXXXXXXXXX##
       ##########
__________
XXXXXXXXXXXXX#
X       X######
XXXXXXXXXXXXXXX#
____
  XXXXXXXXXX
  X        X
  X  XXXX  X
  X X####X X
  XXXXXXXXXX
__
       XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
      XXXX#######XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
      X###  #    ##############XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
     X######X#    #XXXXXXXXXXXXXXXXXXXX
     XXXXXXXX#     #######XX
     X######X#    #XXXXXXX
      X###  #    ##X
      XXXX#######XX
       XXXXXXXXXX

__________
      #XXXXXXXXXX
     #XXXX       XX
     #X            X
    #X      X      XXXXXXX
    #XXXXXXXX             XX
    #X      X      XXXXXXX
     #X            X
     #XXXX       XX
      #XXXXXXXXXX
__________

It is correct?

Moha · Post by **Moha** » Tue Sep 18, 2007 8:10 am

Could anybody test these inputs? I am getting PE.
^ is end of line.
Inputs:

Code: Select all

8

  XXXXXXXXXXXX
  X           X
  X           X         X
  X           X
  X   XXXXX   X
  X   X       X
  X   X *
  X   X       X
  X   XXXXX   X
  X           X
  X           X        X
  X           X
  XXXXXXXXXXXX

__________

  XXX
  X X   *
  X

__________

   *
__________

  XXXXXXXXXX
  X        X
  X XXXXXX X
  X X *  X X
  XXXXXXXXXX

__________
XXXXXXXXXXXXX
X       X  *
XXXXXXXXXXXXXXX
____ 


XXXXXXX
X  *  X
XXXXXXX

__________

       XXXXXXXXXX
      XXXX       XX
      X            X
     X      X      XXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX      *XX
       XXXXXXXXXX

__________

       XXXXXXXXXX
 *    XXXX       XX
      X            X
     X      X      XXXXXXX
     XXXXXXXX             XX
     X      X      XXXXXXX
      X            X
      XXXX       XX
       XXXXXXXXXX

__________

Outputs:

Code: Select all

  ############^
 #XXXXXXXXXXXX#^
 #X###########X#        #^
 #X#         #X#       #X#^
 #X#  #####  #X#        #^
 #X# #XXXXX# #X#^
 #X# #X####  #X#^
 #X# #X#      #^
 #X# #X####  #X#^
 #X# #XXXXX# #X#^
 #X#  #####  #X#       #^
 #X#         #X#      #X#^
 #X###########X#       #^
 #XXXXXXXXXXXX#^
  ############^
__________^
  ###^
 #XXX#^
 #X#X#   ^
 #X##^
  #^
__________^
^
    ^
__________^
^
  XXXXXXXXXX^
  X        X^
  X XXXXXX X^
  X X####X X^
  XXXXXXXXXX^
^
__________^
XXXXXXXXXXXXX#^
X       X######^
XXXXXXXXXXXXXXX#^
____ ^
^
^
XXXXXXX^
X#####X^
XXXXXXX^
^
__________^
^
       XXXXXXXXXX^
      XXXX#######XX^
      X###  #    ##X^
     X######X#    #XXXXXXX^
     XXXXXXXX#     #######XX^
     X######X#    #XXXXXXX^
      X###  #    ##X^
      XXXX#######XX^
       XXXXXXXXXX^
^
__________^
       ##########^
      #XXXXXXXXXX##^
     #XXXX       XX#^
     #X            X######^
    #X      X      XXXXXXX##^
    #XXXXXXXX             XX#^
    #X      X      XXXXXXX##^
     #X            X######^
     #XXXX       XX#^
      #XXXXXXXXXX##^
       ##########^
__________^

OJ Board

782 - Contour Painting

782 - Runtime Error (SIGSEGV)

782 - Runtime Error

782 - Runtime Error

782 got Runtime Error (SIGSEGV),help me plz,thanx

sample input/output for problem 782