183 - Bit Maps

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

Moderator: Board moderators

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am

183

Post by monika » Thu Jul 25, 2002 8:16 am

Hi,

I'm getting WA for 183.

Could someone provide me some good sample input/output for this problem, or let me know, what all tricks could be involved here?


Thanks,
Monika

monika
New poster
Posts: 13
Joined: Tue Jul 23, 2002 9:45 am

183

Post by monika » Thu Jul 25, 2002 9:03 am

Hi,

Thanks for the reply.
But I've tried this, and I get the original bitmap back.
I've even tried with 200 X 200 matrix, and I'm able to convert it from B to D and vice versa.

I'm listing my program below. (although it is quite long), but please let me know, if you could identify some problem with this.....
------------------------
/* @JUDGE_ID: 21235WP 183 C */

/* BIT MAPS */

/* @BEGIN_OF_SOURCE_CODE */


#include <stdio.h>
#include <string.h>
#include <math.h>


struct node{
int row_start, row_end, col_start, col_end;
struct node* next;
};

struct node* stack=NULL;

int matrix[200][200];
void push(int, int, int, int);
void pop(int*, int*, int*, int*);

void main()
{
void decomposematrix();
void fillsubmatrix(int);
int ismatrixfull(int, int);
void printBitmapB(int, int);
void printBitmapD(int, int);

int rows, cols;
char bitmap[40000], temp[55];

char c;
int i,j,k;

bitmap[0]='\0';
temp[0]='\0';
while( (c=getchar())!= '#' )
{
memset(matrix, -1, sizeof(matrix));
scanf("%d %d", &rows, &cols);
if( c == 'B' )
{
/* Simple Bitmap */
do{
scanf("%s", temp);
strcat(bitmap, temp);
}while( strlen(bitmap) < (rows * cols) );

for(i=0,k=0;i<rows;i++)
for(j=0;j<cols;j++)
matrix[j] = bitmap[k++];

printBitmapD(rows, cols);
}
else if ( c == 'D' )
{
/* Decomposed Bitmap */
push(0, rows-1, 0, cols-1);
do{
scanf("%s", temp);

/* Fill Bitmap D */
for(k=0; k< strlen(temp); k++)
{
if( temp[k] == 'D' )
decomposematrix();
else
fillsubmatrix( temp[k] );
}

}while( ! ismatrixfull(rows, cols) );

printBitmapB(rows, cols);
}
fflush(stdin);
}
}


void printBitmapB(int rows, int cols)
{
int i, j;

printf("B %4d %4d", rows, cols);
for(i=0; i<rows; i++)
for(j=0; j<cols; j++)
{
fflush(stdout);
if( j%50 == 0)
printf("\n");
printf("%d", matrix[j]-'0');
}
printf("\n");

}

void printBitmapD(int rows, int cols)
{
int r_start, r_end, c_start, c_end, r_div, c_div;
int i,j,num,split=0;
int onerow, onecol;

char str[50000], temp[2];
str[0]='\0';
temp[0]='\0';

printf("D %4d %4d", rows, cols);

push(0, rows-1, 0, cols-1);
while(stack != NULL)
{
split=0;
pop(&r_start, &r_end, &c_start, &c_end);
num = matrix[r_start][c_start];
for(i=r_start; i<=r_end; i++)
for(j=c_start; j<=c_end; j++)
if( matrix[j] != num )
split=1;


if (split)
{
strcat(str, "D");
r_div = r_start + ((r_end - r_start)/2);
c_div = c_start + ((c_end - c_start)/2);

onerow = ((r_start == r_div) && (r_div == r_end))?1:0;
onecol = ((c_start == c_div) && (c_div == c_end))?1:0;

if(!onerow && !onecol)
push( r_div+1, r_end, c_div+1, c_end);

if( !onerow )
push( r_div+1, r_end, c_start, c_div);

if( !onecol )
push( r_start, r_div, c_div+1, c_end);

push(r_start, r_div, c_start, c_div);
}
else
{
sprintf(temp,"%d",num-'0' );
strcat(str,temp);
}

}
str[strlen(str)]='\0';

for(i=0; i<strlen(str); i++)
{
if( i%50 == 0 )
printf("\n");
printf("%c", str);
}
printf("\n");
}

int ismatrixfull(int rows, int cols)
{
int i,j;

for(i=0; i<rows; i++)
for(j=0; j<cols; j++)
if(matrix[j] == -1 )
return 0;

return 1;

}


void fillsubmatrix(int num)
{
int r_start, r_end, c_start, c_end;
int i,j;

pop(&r_start, &r_end, &c_start, &c_end);

for(i=r_start; i<=r_end; i++)
for(j=c_start; j<=c_end; j++)
matrix[j] = num;


}

void decomposematrix()
{
int r_start, r_end, c_start, c_end;
int r_div, c_div;
int onerow=0, onecol=0;

pop(&r_start, &r_end, &c_start, &c_end);

r_div = r_start + ((r_end - r_start)/2);
c_div = c_start + ((c_end - c_start)/2);

onerow = ( (r_start == r_div) && (r_div == r_end))? 1:0;
onecol = ( (c_start == c_div) && (c_div == c_end))? 1:0;

/* push four quarters in reverse order. i.e. 4th, 3rd, 2nd, 1st. */
if( !onerow && !onecol )
push( r_div+1, r_end, c_div+1, c_end);

if( ! onerow )
push( r_div+1, r_end, c_start, c_div);

if( ! onecol )
push( r_start, r_div, c_div+1, c_end);

push(r_start, r_div, c_start, c_div);

}


void push(int r_start, int r_end, int c_start, int c_end)
{
struct node* ptr;

ptr = (struct node*)malloc(sizeof(struct node));
ptr->row_start = r_start;
ptr->row_end = r_end;
ptr->col_start = c_start;
ptr->col_end = c_end;
ptr->next=stack;
stack=ptr;

}

void pop(int* r_start, int* r_end, int* c_start, int* c_end)
{
struct node *ptr;

/*assuming stack is not empty!
if it can be, then do error-handling */

*r_start = stack->row_start;
*r_end = stack->row_end;
*c_start = stack->col_start;
*c_end = stack->col_end;

ptr = stack;
stack = stack->next;
free(ptr);

}

anubis_kanuII
New poster
Posts: 3
Joined: Tue Dec 17, 2002 7:25 pm
Location: Brazil

Problem 183 (Bit maps) - WA - Could anyone help me?!?!

Post by anubis_kanuII » Sun Jan 12, 2003 6:30 am

I've got WA whit my algorithm, but it solved all the inputs I've created. Is there any trick? I also don't know if it's a problem whit the output format. This is my code :
/---------------------------------------------------------------------------------/
[c]#include <stdio.h>
#include <stdlib.h>

char s[60];/**/
char buff[60];
int out=0,ind=0;
typedef unsigned char matriz [250][250];
/*---------------------------------------------------------------------------*/
void b2d(matriz mat, int lin0, int linf, int col0, int colf){
unsigned i,j,deltalin,deltalin2,deltacol,deltacol2,linmeio,colmeio;
unsigned char cor=mat[lin0][col0];
unsigned char d=0;

for(i=lin0;i<=linf;i++)
for(j=col0;j<=colf;j++)
if(cor!=mat[j])
{
d=1;
break;
}

if(!d){
out++;
printf("%d",cor); /**/
if(out==50){
printf("\n");/**/
out=0;
}
return;
}
printf("D");
deltalin=(linf+lin0-1);
deltalin2=(linf-lin0+1);
deltacol=(colf+col0-1);
deltacol2=(colf-col0+1);
linmeio=(deltalin/2 + deltalin2 % 2);
colmeio=(deltacol/2 + deltacol2 % 2);

b2d(mat,lin0,linmeio,col0,colmeio);
if(colmeio<colf)
b2d(mat,lin0,linmeio,colmeio+1,colf);
if(linmeio<linf)
b2d(mat,linmeio+1,linf,col0,colmeio);
if(linmeio<linf && colmeio<colf)
b2d(mat,linmeio+1,linf,colmeio+1,colf);
}
/*---------------------------------------------------------------------------*/
void d2b(matriz *mat,int lin0, int linf, int col0, int colf){
unsigned i,j,deltalin,deltalin2,deltacol,deltacol2,linmeio,colmeio;
unsigned char c,d=0;
c=s[ind++];
if(c=='0'||c=='1'){
for(i=lin0;i<=linf;i++)
for(j=col0;j<=colf;j++){

(*mat)[j]=(c-'0');}

return;
}
deltalin=(linf+lin0-1);
deltalin2=(linf-lin0+1);
deltacol=(colf+col0-1);
deltacol2=(colf-col0+1);
linmeio=(deltalin/2 + deltalin2 % 2);
colmeio=(deltacol/2 + deltacol2 % 2);

d2b(mat,lin0,linmeio,col0,colmeio);
if(colmeio<colf)
d2b(mat,lin0,linmeio,colmeio+1,colf);
if(linmeio<linf)
d2b(mat,linmeio+1,linf,col0,colmeio);
if(linmeio<linf && colmeio<colf)
d2b(mat,linmeio+1,linf,colmeio+1,colf);

}
/*---------------------------------------------------------------------------*/
int main (){
matriz mat;
/*entrada*/
for(;;){
char caso;
int lin,col;
int i,j;
A:
scanf("%c %d %d",&caso,&lin,&col);
if(caso=='#')break;
if(caso=='\n')goto A;
if(caso=='B'){
out=0;
for(i=1;i<=lin;i++)
for(j=1;j<=col;j++)
scanf("%1d",&(mat[j]));
printf("D%4d%4d\n",lin,col);
b2d(mat,1,lin,1,col);
if(out!=0)printf("\n");

}/*if*/
else {
int i,j;
out=ind=0;

scanf("%s",s);
printf("B%4d%4d\n",lin,col);
d2b(&mat,1,lin,1,col);

for(i=1;i<=lin;i++){
for(j=1;j<=col;j++){
out++;
printf("%d",mat[j]);/**/
if(out==50){printf("\n");
out=0;}
}
}
if(out!=0)printf("\n");/**/
}


}
return 0;
}[/c]


Thanks!! :)
Anubis

anubis_kanuII
New poster
Posts: 3
Joined: Tue Dec 17, 2002 7:25 pm
Location: Brazil

183 - Bit Maps

Post by anubis_kanuII » Sun Jan 12, 2003 6:32 am

I've got WA with my algorithm, but it solved all the inputs I've created. Is there any trick? I also don't know if it's a problem with the output format. This is my code :
/---------------------------------------------------------------------------------/
[c]#include <stdio.h>
#include <stdlib.h>

char s[60];/**/
char buff[60];
int out=0,ind=0;
typedef unsigned char matriz [250][250];
/*---------------------------------------------------------------------------*/
void b2d(matriz mat, int lin0, int linf, int col0, int colf){
unsigned i,j,deltalin,deltalin2,deltacol,deltacol2,linmeio,colmeio;
unsigned char cor=mat[lin0][col0];
unsigned char d=0;

for(i=lin0;i<=linf;i++)
for(j=col0;j<=colf;j++)
if(cor!=mat[j])
{
d=1;
break;
}

if(!d){
out++;
printf("%d",cor); /**/
if(out==50){
printf("\n");/**/
out=0;
}
return;
}
printf("D");
deltalin=(linf+lin0-1);
deltalin2=(linf-lin0+1);
deltacol=(colf+col0-1);
deltacol2=(colf-col0+1);
linmeio=(deltalin/2 + deltalin2 % 2);
colmeio=(deltacol/2 + deltacol2 % 2);

b2d(mat,lin0,linmeio,col0,colmeio);
if(colmeio<colf)
b2d(mat,lin0,linmeio,colmeio+1,colf);
if(linmeio<linf)
b2d(mat,linmeio+1,linf,col0,colmeio);
if(linmeio<linf && colmeio<colf)
b2d(mat,linmeio+1,linf,colmeio+1,colf);
}
/*---------------------------------------------------------------------------*/
void d2b(matriz *mat,int lin0, int linf, int col0, int colf){
unsigned i,j,deltalin,deltalin2,deltacol,deltacol2,linmeio,colmeio;
unsigned char c,d=0;
c=s[ind++];
if(c=='0'||c=='1'){
for(i=lin0;i<=linf;i++)
for(j=col0;j<=colf;j++){

(*mat)[j]=(c-'0');}

return;
}
deltalin=(linf+lin0-1);
deltalin2=(linf-lin0+1);
deltacol=(colf+col0-1);
deltacol2=(colf-col0+1);
linmeio=(deltalin/2 + deltalin2 % 2);
colmeio=(deltacol/2 + deltacol2 % 2);

d2b(mat,lin0,linmeio,col0,colmeio);
if(colmeio<colf)
d2b(mat,lin0,linmeio,colmeio+1,colf);
if(linmeio<linf)
d2b(mat,linmeio+1,linf,col0,colmeio);
if(linmeio<linf && colmeio<colf)
d2b(mat,linmeio+1,linf,colmeio+1,colf);

}
/*---------------------------------------------------------------------------*/
int main (){
matriz mat;
/*entrada*/
for(;;){ /* <-- That should not be an emoticon ... */
char caso;
int lin,col;
int i,j;
A:
scanf("%c %d %d",&caso,&lin,&col);
if(caso=='#')break;
if(caso=='\n')goto A;
if(caso=='B'){
out=0;
for(i=1;i<=lin;i++)
for(j=1;j<=col;j++)
scanf("%1d",&(mat[j]));
printf("D%4d%4d\n",lin,col);
b2d(mat,1,lin,1,col);
if(out!=0)printf("\n");

}/*if*/
else {
int i,j;
out=ind=0;

scanf("%s",s);
printf("B%4d%4d\n",lin,col);
d2b(&mat,1,lin,1,col);

for(i=1;i<=lin;i++){
for(j=1;j<=col;j++){
out++;
printf("%d",mat[j]);/**/
if(out==50){printf("\n");
out=0;}
}
}
if(out!=0)printf("\n");/**/
}


}
return 0;
}[/c]


Thanks!! :)
Anubis

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

183 - BitMaps

Post by titid_gede » Thu Apr 24, 2003 7:54 am

are there tricky inputs for this problem?
how is the input contains 3 lines? does the output should contains 3 lines too?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Fri Apr 25, 2003 4:35 pm

i've fixed my problems such as a line will consist at most 50 characters, but still i got WA. are there tricky inputs?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sat Apr 26, 2003 4:02 pm

finally got accepted. there is small mistake in my code and my understanding about problem :)
Kalo mau kaya, buat apa sekolah?

acm_rules
New poster
Posts: 3
Joined: Fri Aug 01, 2003 9:34 am

BitMaps 183 - WA, HELP!

Post by acm_rules » Fri Aug 01, 2003 9:45 am

I've tested my code with a lot of inputs and It's working fine, but I keep getting Wrong Answer. I'd really apreciate it if someone could check my code and tell me if there's something wrong.
Thanks in advance. :)

Code: Select all

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

char bmp[200][200];

void code(int x, int y, int row, int col)
{
	int row1, row2, col1, col2;
	
	for(int i=x; i < x+row; i++)
		for(int j=y; j < y+col; j++)
			if(bmp[i][j] != bmp[x][y]) 
			{
				row2 = row/2;
				row1 = row - row2;
				col2 = col/2;
				col1 = col - col2;
			
				cout << 'D';
				code(x, y, row1, col1);
				code(x, y+col1, row1, col2);
				code(x+row1, y, row2, col1);
				code(x+row1, y+col1, row2, col2);
				return;
			}
	
	if(col != 0 && row != 0)
		cout << bmp[x][y];
}

void decode(int x, int y, int row, int col)
{
	int row1, row2, col1, col2;

	if(row == 0 || col == 0)
		return;
	
	char input;
	cin >> input;
	if(input == 'D') 
	{
		row2 = row/2;
		row1 = row - row2;
		col2 = col/2;
		col1 = col - col2;
		
		decode(x, y, row1, col1);
		decode(x, y+col1, row1, col2);
		decode(x+row1, y, row2, col1);
		decode(x+row1, y+col1, row2, col2);
	}
	else if(input == '0' || input == '1')
	{
		for(int a=x; a < x+row; a++)
			for(int b=y; b < y+col; b++) 
				bmp[a][b] = input;
	}
}

int main()
{
	int i, j, row, col;
	char ch;

	while(true)
	{
		cin >> ch;
		
		if(ch == '#')
			return 0;
		
		cin >> row >> col;
		switch(ch)
		{
		case 'D':
			cout << "B" << setw(4) << row << setw(4) << col << endl;
			
			decode(0, 0, row, col);
			for(i=0; i < row; i++)
				for(j=0; j < col; j++)
					cout << bmp[i][j];
			cout << endl;
			break;
		case 'B':
			for(i=0; i < row; i++)
				for(j=0; j < col; j++)
					cin >> bmp[i][j];
			
			cout << "D" << setw(4) << row << setw(4) << col << endl;
			code(0, 0, row, col);
			cout << endl;
			break;
		}
	}
	return 0;
}

zacharyleung
New poster
Posts: 14
Joined: Tue Feb 03, 2004 3:43 am

Clarification for 183 (Bit Maps)

Post by zacharyleung » Sat Mar 27, 2004 7:34 am

I was getting stuck on this problem, and I finally figured out why I was getting WA. The reason was that if the bit map contians more than 50 characters, they would like the answer to be something like the following:

D 3 30
DDDDD01D01DD01D01DDD01D01DD010DDD10D10DD10D10DDD10
D10DD101DDDD10D10D1D01DDD01D01DD010DDD01D01DD01D01
DDD01D01DD010DDDD01D01DD01D01DDD01D01DD010DDDD10D1
0D1D01DDD01D01DD010
B 6 20
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111
11111111111111111111

that is, for every 50 characters, print a newline.

If you're stuck on this, hope this helps you! :D
For God so loved the world, that he gave his only Son, that whoever believes in him should not perish but have eternal life.
(John 3:16)

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

183 WA.....

Post by ibroker » Fri Feb 24, 2006 5:36 am

What is wrong!
any have some tricky data?

#include <string.h>
#include <stdio.h>

#define M 500000

char c;
int yy, xx;
char temp[M];
int str;
char path[M];
int dep;
char data[300][300];
int p;

void make(int, int, int, int);
void filled(int, int, int, int);
int main()
{
char tmp[300];
int i, j;

gets(temp);
while(1)
{
sscanf(temp, "%c %d %d", &c, &yy, &xx);
if(c=='#') break;
str=0;
while(gets(tmp))
{
if(tmp[1]==' ' || tmp[1]==0) break;
else
{
for(i=0; i<strlen(tmp); i++) temp[str++]=tmp;
}
}
temp[str]=NULL;

if(c=='B')
{
dep=0;
for(i=1; i<=yy; i++){ for(j=1; j<=xx; j++) data[j]=temp[dep++]; }
dep=0;
filled(1, 1, xx, yy);
printf("D%4d%4d\n", yy, xx); p=0;
for(i=0; i<dep; i++)
{
printf("%c", path);
p++; if(p==50){ printf("\n"); p=0; }
path=0;
}
if(p!=0) printf("\n");
}
else if(c=='D')
{
dep=0;
make(1, 1, xx, yy);
printf("B%4d%4d\n", yy, xx); p=0;
for(i=1; i<=yy; i++)
{
for(j=1; j<=xx; j++)
{
printf("%c", data[j]);
p++; if(p==50){ printf("\n"); p=0; }
data[j]=0;
}
}
if(p!=0) printf("\n");
}
if(tmp[0]=='#') break;
else
{
for(i=0; i<strlen(tmp); i++) temp=tmp;
temp=NULL;
}
}

return 0;
}

void make(int lx, int ly, int rx, int ry)
{
int i, j;
if(dep>=str) return;

if(temp[dep]=='D')
{
dep++;
if(lx!=rx && ly!=ry)
{
make(lx, ly, (lx+rx)/2, (ly+ry)/2);
make((lx+rx)/2+1, ly, rx, (ly+ry)/2);
make(lx, (ly+ry)/2+1, (lx+rx)/2, ry);
make((lx+rx)/2+1, (ly+ry)/2+1, rx, ry);
}
else if(lx!=rx)
{
make(lx, ly, (lx+rx)/2, ry);
make((lx+rx)/2+1, ly, rx, ry);
}
else if(ly!=ry)
{
make(lx, ly, rx, (ly+ry)/2);
make(lx, (ly+ry)/2+1, rx, ry);
}
}
else if(temp[dep]=='0')
{
dep++;
for(i=ly; i<=ry; i++){ for(j=lx; j<=rx; j++) data[j]='0'; }
}
else if(temp[dep]=='1')
{
dep++;
for(i=ly; i<=ry; i++){ for(j=lx; j<=rx; j++) data[i][j]='1'; }
}
}

void filled(int lx, int ly, int rx, int ry)
{
int i, j;
bool no1, no2;

no1=0; no2=0;
for(i=ly; i<=ry; i++)
{
for(j=lx; j<=rx; j++)
{
if(data[i][j]=='0') no1=1;
else if(data[i][j]=='1') no2=1;
}
}
if(no1 && no2)
{
path[dep++]='D';
if(lx!=rx && ly!=ry)
{
filled(lx, ly, (lx+rx)/2, (ly+ry)/2);
filled((lx+rx)/2+1, ly, rx, (ly+ry)/2);
filled(lx, (ly+ry)/2+1, (lx+rx)/2, ry);
filled((lx+rx)/2+1, (ly+ry)/2+1, rx, ry);
}
else if(lx!=rx)
{
filled(lx, ly, (lx+rx)/2, ry);
filled((lx+rx)/2+1, ly, rx, ry);
}
else if(ly!=ry)
{
filled(lx, ly, rx, (ly+ry)/2);
filled(lx, (ly+ry)/2+1, rx, ry);
}
}
else if(no1)
{
path[dep++]='0';
}
else if(no2)
{
path[dep++]='1';
}
}

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

Post by sds1100 » Fri Mar 03, 2006 8:30 am

sorry i don't know your program

User avatar
gradientcurl
New poster
Posts: 16
Joined: Mon Jun 26, 2006 9:33 am
Contact:

183 WA in 0.000 (minimum mem)

Post by gradientcurl » Sun Dec 17, 2006 5:30 pm

I have been running test cases thru my prog and they got back agreeable results, but what I do not understand is my prog becomes WA in 0.000 CPU (minimum memory). is there some trick to the test cases? does it include zero sized bitmaps? if so is the null string being output? or no blank line?

Code: Select all

#include <cstdio>
#define MAXSIZE 200
#define MAXLENGTH 55
using namespace std;

struct BITMAP
{
	bool grid[MAXSIZE][MAXSIZE];
	int rowdim,coldim;
};

void parseBitmap(BITMAP &a)
{
	char ch;
	for(int i=0;i<a.rowdim;i++)
		for(int j=0;j<a.coldim;j++)
		{
			scanf(" %c",&ch);
			a.grid[i][j] = ch-'0';
		}
}

void genDecomp(const BITMAP &a,int x,int y,int row,int col)
{
	if(row<1||col<1)
		return;
	bool orig = a.grid[x][y];

	for(int i=0;i<row;i++)
		for(int j=0;j<col;j++)
			if(orig!=a.grid[x+i][y+j])
			{
				putchar('D');
				genDecomp(a,x,y,(row+1)/2,(col+1)/2);
				genDecomp(a,x,y+(col+1)/2,(row+1)/2,col-(col+1)/2);
				genDecomp(a,x+(row+1)/2,y,row-(row+1)/2,(col+1)/2);
				genDecomp(a,x+(row+1)/2,y+(col+1)/2,row-(row+1)/2,col-(col+1)/2);
				return;
			}
	putchar(orig?'1':'0');
}

void fillBitmap(BITMAP &a,int x,int y,int row,int col)
{
	if(row<1||col<1)
		return;
	char ch;
	scanf(" %c",&ch);
	switch(ch)
	{
		case '1': case '0':
			for(int i=0;i<row;i++)
				for(int j=0;j<col;j++)
					a.grid[x+i][y+j] = ch-'0';
			break;
		case 'D':
			fillBitmap(a,x,y,(row+1)/2,(col+1)/2);
			fillBitmap(a,x,y+(col+1)/2,(row+1)/2,col-(col+1)/2);
			fillBitmap(a,x+(row+1)/2,y,row-(row+1)/2,(col+1)/2);
			fillBitmap(a,x+(row+1)/2,y+(col+1)/2,row-(row+1)/2,col-(col+1)/2);
			break;
	}
}

void printBitmap(const BITMAP &a)
{
	for(int i=0;i<a.rowdim;i++)
		for(int j=0;j<a.coldim;j++)
			putchar(a.grid[i][j]?'1':'0');
}

int main()
{
	BITMAP bitmap;
	char mode;

	while(scanf(" %c %d %d",&mode,&bitmap.rowdim,&bitmap.coldim)==3)
	{
		printf("%c%4d%4d\n",mode=='B'?'D':'B',bitmap.rowdim,bitmap.coldim);
		if(mode=='B')
		{
			parseBitmap(bitmap);
			genDecomp(bitmap,0,0,bitmap.rowdim,bitmap.coldim);
		}
		else
		{
			fillBitmap(bitmap,0,0,bitmap.rowdim,bitmap.coldim);
			printBitmap(bitmap);
		}
		putchar('\n');
	}
	return 0;
}
below is a test case file:

Code: Select all

B 0 0
B 16 16
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110000
0000000011110000
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110011
0000000011110011
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 16 16
0000000011110010
0000000011110011
0000000011110000
0000000011110000
0000000011111111
0000000011111111
0000000011111111
0000000011111111
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
B 1 1
1
B 2 2
0001
B 3 3
001101010
B 4 4
0001110101010101
B 5 5
0010011101110100111110101
B 1 10
1001010101
B 10 1
0100011010
B 2 20
00111011101001101010
11010001010101000010
B 20 2
00111000000010100000
01011111000001010001
D  16  16
0
D  16  16
D0100
D  16  16
D0D101100
D  16  16
D0D1D01001100
D  16  16
D0D1D0D1011001100
D   1   1
1
D   2   2
D0001
D   3   3
DD00101D010
D   4   4
DD0011D0101D0101D0101
D   5   5
DDD0011110D0D0110DD011D101D1101
D   1  10
DDDD100D10DDD101D01
D  10   1
DDDD0100DD10D10
D   2  20
DDDD011DDD011D10DDDD1001DDD010D10DDD10D10DD01D01DDDD010D10D0D10
D  20   2
DDDDD0110DDD0110DDDD01000DDD01D100DD1D10DDD011D01
#
And here is my output (note that the input for the first half of B gives the output for D in the previous file)

Code: Select all

D   0   0

D  16  16
0
D  16  16
D0100
D  16  16
D0D101100
D  16  16
D0D1D01001100
D  16  16
D0D1D0D1011001100
D   1   1
1
D   2   2
D0001
D   3   3
DD00101D010
D   4   4
DD0011D0101D0101D0101
D   5   5
DDD0011110D0D0110DD011D101D1101
D   1  10
DDDD100D10DDD101D01
D  10   1
DDDD0100DD10D10
D   2  20
DDDD011DDD011D10DDDD1001DDD010D10DDD10D10DD01D01DDDD010D10D0D10
D  20   2
DDDDD0110DDD0110DDDD01000DDD01D100DD1D10DDD011D01
B  16  16
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
B  16  16
0000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
B  16  16
0000000011110000000000001111000000000000111100000000000011110000000000001111111100000000111111110000000011111111000000001111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
B  16  16
0000000011110011000000001111001100000000111100000000000011110000000000001111111100000000111111110000000011111111000000001111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
B  16  16
0000000011110010000000001111001100000000111100000000000011110000000000001111111100000000111111110000000011111111000000001111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
B   1   1
1
B   2   2
0001
B   3   3
001101010
B   4   4
0001110101010101
B   5   5
0010011101110100111110101
B   1  10
1001010101
B  10   1
0100011010
B   2  20
0011101110100110101011010001010101000010
B  20   2
0011100000001010000001011111000001010001

Hackson
New poster
Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

Post by Hackson » Sat May 05, 2007 11:34 am

Please set the width to be 50 characters.
Try and see if you still get any WAs.
Solving problem is a no easy task...

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo » Thu Jun 28, 2007 8:25 pm

I get the following outputs for the above inputs:

Code: Select all

D   0   0

D  16  16
0
D  16  16
D0100
D  16  16
D0D101100
D  16  16
D0D1D01001100
D  16  16
D0D1D0D1011001100
D   1   1
1
D   2   2
D0001
D   3   3
DD00101D010
D   4   4
DD0011D0101D0101D0101
D   5   5
DDD0011110D0D0110DD011D101D1101
D   1  10
DDDD100D10DDD101D01
D  10   1
DDDD0100DD10D10
D   2  20
DDDD011DDD011D10DDDD1001DDD010D10DDD10D10DD01D01DD
DD010D10D0D10
D  20   2
DDDDD0110DDD0110DDDD01000DDD01D100DD1D10DDD011D01
B  16  16
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111111110000000011111111000000001111111100
00000011111111000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100000000000011110000000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100110000000011110011000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B  16  16
00000000111100100000000011110011000000001111000000
00000011110000000000001111111100000000111111110000
00001111111100000000111111110000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
000000
B   1   1
1
B   2   2
0001
B   3   3
001101010
B   4   4
0001110101010101
B   5   5
0010011101110100111110101
B   1  10
1001010101
B  10   1
0100011010
B   2  20
0011101110100110101011010001010101000010
B  20   2
0011100000001010000001011111000001010001
Are they okay? I am getting WAs. Can someone provide some more IOs??? thanks in advance...

[EDIT] outputs posted above are okay... My problem was output formatting... though I think it should be PE...
regards,
nymo

hotwxn711
New poster
Posts: 3
Joined: Tue Jul 21, 2009 1:02 am

Re: 183

Post by hotwxn711 » Wed Jul 29, 2009 10:10 am

If the length of the map is the multiplication of 50, your code will output two new lines.

Post Reply

Return to “Volume 1 (100-199)”