## 806 - Spatial Structures

Moderator: Board moderators

Yaron Wittenstein
New poster
Posts: 18
Joined: Wed Jul 21, 2004 5:09 pm
Contact:

### 806 - Spatial Structures

Code: Select all

``````#include <stdio.h>

#define  MAXN  64

#define  white  0
#define  black  1

typedef int color;

color pixel[MAXN][MAXN]; /* for storing the image */

long sequence[MAXN * MAXN + 1];

char line[MAXN + 1]; /* for reading the input */

unsigned int size; /* saves the size of the sequence */
int n;  	   /* size of the square */

void init()        /* draws the image in white */
{
unsigned int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
pixel[i][j] = white;
}
}
}

void swap(unsigned long *a, unsigned long *b)
{
unsigned long tmp =   *a;
*a =    *b;
*b =   tmp;
}

void sort() /* prints the sequence in ascending order */
{
unsigned int  i, j;
unsigned long imin;
for(i = 0; i < size - 1; i++) {
imin = i;
for(j = i + 1; j < size; j++) {
if (sequence[imin] > sequence[j]) {
imin = j;
}
}
if (imin != i) {
swap(&sequence[imin], &sequence[i]);
}
}
}

void printSequence()
{
unsigned int i, j, k = 0;

for(i = 0; i < (size / 12); i++) {
for(j = 0; j < 12; j++) {
printf("%ld ", sequence[k++]);
}
printf("\n");
}

if ((size % 12) == 0) return;
for(i = 0; i < (size % 12); i++) {
printf("%d ", sequence[k++]);
}
printf("\n");
}

void printImage()
{
unsigned int i, j;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
printf("%c", pixel[i][j] == white ? '.' : '*' );
}
printf("\n");
}
}

unsigned long base5Tobase10(unsigned long num)
{
unsigned long new_num = 0;
unsigned long base = 1;

while (num != 0) {
new_num  = new_num + (num % 10) * base;
base *= 5;
num /= 10;
}
return new_num;
}

unsigned long base10Tobase5(unsigned long num)
{
unsigned long new_num = 0;
unsigned long base = 1;

while (num != 0) {
new_num = new_num + base * (num % 5);
num = (num - (num % 5)) / 5;
base *= 10;
}
return new_num;
}

void descryptSequence()
{
unsigned int i;
for(i = 0; i < size; i++) {
sequence[i] = base10Tobase5(sequence[i]);
}
}

/* calculates the square to be filled black */
void calcSquare(int* x1, int* y1, int* x2, int* y2, unsigned long path)
{
while (path != 0) {
switch (path % 10) {
case 1: *x2 = (*x1 + *x2 - 1) / 2;
*y2 = (*y1 + *y2 - 1) / 2;
break;
case 2:
*x1 = (*x1 + *x2 + 1) / 2;
*y2 = (*y1 + *y2 - 1) / 2;
break;
case 3:
*y1 = (*y1 + *y2 + 1) / 2;
*x2 = (*x1 + *x2 - 1) / 2;
break;
case 4:
*x1 = (*x1 + *x2 + 1) / 2;
*y1 = (*y1 + *y2 + 1) / 2;
break;
}
path /= 10;
}
}

/* (x1, y1)  (x2, y2) are the coordinates of the square  */
/* fills the square black 			         */
void fillSquare(int x1, int y1, int x2, int y2)
{
int i, j;
for(i = y1; i <= y2; i++) {
for(j = x1; j <= x2; j++) {
pixel[i][j] = black;
}
}
}

void drawImage()  /* prints the image to the screen */
{
unsigned int i;
int x1, y1, x2, y2;
for(i = 0; i < size; i++) {
x1 = 0;
y1 = 0;
x2 = n - 1;
y2 = n - 1;
calcSquare(&x1, &y1, &x2, &y2, sequence[i]);
fillSquare(x1, y1, x2, y2);
}
}

/* checks if the square is one color on success returns in c the color */
int OneColor(int x1, int y1, int x2, int y2, color* c)
{
int i, j;
color square_color = pixel[y1][x1];
for(i = y1; i <= y2; i++) {
for(j = x1; j <= x2; j++) {
if (pixel[i][j] != square_color) {
return 0;
}
}
}
(*c) = square_color;
return 1;
}

void Image2Numbers(int x1, int y1, int x2, int y2, unsigned long path, unsigned long base)
{
color c;
if ( OneColor(x1, y1, x2, y2, &c) ) {
if (c == black) {
sequence[size] = base5Tobase10(path);
size++;
}
return;
}

if (base != 0) {
base *= 10;
}
else {
base = 1;
}
Image2Numbers(x1, y1, (x1 + x2 - 1) / 2, (y1 + y2 - 1) / 2, path + base * 1, base);
Image2Numbers((x1 + x2 + 1) / 2, y1, x2, (y1 + y2 - 1) / 2, path + base * 2, base);
Image2Numbers(x1, (y1 + y2 + 1) / 2, (x1 + x2 - 1) / 2, y2, path + base * 3, base);
Image2Numbers((x1 + x2 + 1) / 2, (y1 + y2 + 1) / 2, x2, y2, path + base * 4, base);
}

int main()
{
unsigned int i, j, case_num = 0;

scanf("%d", &n);
while (n != 0) {
if (n > 0) {  /* convert image to sequence */
for(i = 0; i < n; i++) {  /* get image */
scanf("%s", &line);
for(j = 0; j < n; j++) {
pixel[i][j] = (color)(line[j] - '0');
}
}
size = 0;
Image2Numbers(0, 0, n - 1, n - 1, 0, 0);
sort();

printf("Image %d\n", ++case_num);
printSequence();
printf("Total number of black nodes = %d\n", size);
}
else {  /* n < 0 */
n = -n;
size = 0;
init();
while (1) {
scanf("%ld", &sequence[size++]);
if (sequence[size - 1] == -1) {
size--; /* we don't use the -1 */
descryptSequence();
printf("Image %d\n", ++case_num);
drawImage();
printImage();
break;
}
}
}

scanf("%d", &n);
if (n != 0) {  /* end of input */
printf("\n");
}
}

return 0;
}
``````
i get TLE, i think it has something to do with the wau
please try to help me here!!!!!!!!!!!!!!!!!

guayoyo
New poster
Posts: 11
Joined: Wed Aug 17, 2005 5:59 pm
Location: Caracas, Venezuela

### 806 - Spatial Structures - WA

Hi everybody, can someone post some critical input here... I tried everything, but still WA...

Thanks.
10024 - Guayoyo has Curled Up the Cube!

carlke
New poster
Posts: 2
Joined: Fri Mar 16, 2012 8:22 pm

### Re: 806 - Spatial Structures

I have tried many inputs, but still can't find why I got WA.
Can someone give me some inputs to try?
Thanks!

My code:

Code: Select all

``````#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

typedef unsigned int uint;

#define MAX 64
#define NW 1
#define NE 2
#define SW 3
#define SE 4

void code_to_img(int n);
void img_to_code(int n);
void divide(int code,int len, int i, int j);
bool pure(int len, int i, int j);
void pour(int len, int i, int j);
int rev(int code);
int five_to_ten(int num);
int ten_to_five(int num);

int img[MAX][MAX];
vector<int> ans;

int main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

bool first=true;
int count=0;
int n;
while(cin >> n) {
if(n==0) break;
if(first==false) printf("\n\n");
else first=false;
printf("Image %d\n",++count);
if(n>0) {
img_to_code(n);
} else {
code_to_img(n);
}
}
printf("\n");
return 0;
}

void code_to_img(int n) {
n=-n;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
img[i][j]=0;
}
}
int temp;
while(cin >> temp) {
if(temp==-1) break;
temp=ten_to_five(temp);
int len=n;
int i=0,j=0;
while(temp!=0) {
len/=2;
switch(temp%10) {
case SW:
i+=len;
break;
case NE:
j+=len;
break;
case SE:
i+=len;
j+=len;
break;
case NW:
break;
}
temp/=10;
}
pour(len,i,j);
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(img[i][j]==1) printf("*");
else if(img[i][j]==0) printf(".");
else printf("x");
}
if(i!=n-1) printf("\n");
}
}

void img_to_code(int n) {
ans.erase(ans.begin(),ans.end());

char c;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> c;
img[i][j]=c-48;
}
}

divide(0, n, 0,0);
sort(ans.begin(),ans.end());
for(uint i=0; i<ans.size(); i++) {
if(i%12==0&&i!=0) printf("\n");
if(i!=(ans.size()-1) && (i%12!=11)) printf("%d ",ans[i]);
else printf("%d",ans[i]);
}
if(ans.size()!=0) printf("\n");
printf("Total number of black nodes = %d", ans.size());
}

void divide(int code,int len, int i, int j) {
if(pure(len,i,j)==1) {
if(img[i][j]==1) {
ans.push_back(five_to_ten(rev(code)));
}
return;
}
divide(code*10+SE,len/2,i+len/2,j+len/2);
divide(code*10+SW,len/2,i+len/2,j);
divide(code*10+NE,len/2,i,j+len/2);
divide(code*10+NW,len/2,i,j);
}

bool pure(int len, int i, int j) {
bool first=img[i][j];
for(int m=i; m<len+i; m++) {
for(int n=j; n<len+j; n++) {
if(img[m][n]!=first) return false;
}
}
return true;
}

void pour(int len, int i, int j) {
for(int m=i; m<len+i; m++) {
for(int n=j; n<len+j; n++) {
img[m][n]=1;
}
}
}

int rev(int code) {
int temp=0;
while(code/10!=0) {
temp=temp+(code%10);
temp*=10;
code/=10;
}
temp+=code;
return temp;
}

int five_to_ten(int num) {
int temp=0;
int power=0;
while(num/10!=0) {
temp+=((num%10)*pow(5,power));
power++;
num/=10;
}
temp+=((num%10)*pow(5,power));
return temp;
}

int ten_to_five(int num) {
int lastbit;
int out=0;
lastbit = num%5;
if(num/5>0) {
out = ten_to_five(num/5);
}
out = out*10+lastbit;
return out;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 806 - Spatial Structures

There is nothing wrong with this code.
Check input and AC output for thousands of problems on uDebug!

carlke
New poster
Posts: 2
Joined: Fri Mar 16, 2012 8:22 pm

### Re: 806 - Spatial Structures

I found why I got WA.
The judge system doesn't accept programs with correct output.
Base on the prob description, I should always print one newline between testcases,
but the actual situation is somehow different.
Instead of one newline, there is no newline or two newlines base on the type of previous testcase.

Here is the code with wrong(but accepted) output:

Code: Select all

``````#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;

typedef unsigned int uint;

#define MAX 64
#define NW 1
#define NE 2
#define SW 3
#define SE 4

void code_to_img(int n);
void img_to_code(int n);
void divide(int code,int len, int i, int j);
bool pure(int len, int i, int j);
void pour(int len, int i, int j);
int rev(int code);
int five_to_ten(int num);
int ten_to_five(int num);

int img[MAX][MAX];
vector<int> ans;

int main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

bool first=true;
int count=0;
int n;
while(cin >> n) {
if(n==0) break;

if(n>0) {
if(first==false) printf("\n\n");
else first=false;
printf("Image %d\n",++count);
img_to_code(n);
} else {
if(first==false) printf("\n");
else first=false;
printf("Image %d\n",++count);
code_to_img(n);
}
}
printf("\n");
return 0;
}

void code_to_img(int n) {
n=-n;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
img[i][j]=0;
}
}
int temp;
while(cin >> temp) {
if(temp==-1) break;
temp=ten_to_five(temp);
int len=n;
int i=0,j=0;
while(temp!=0) {
len/=2;
switch(temp%10) {
case SW:
i+=len;
break;
case NE:
j+=len;
break;
case SE:
i+=len;
j+=len;
break;
case NW:
break;
}
temp/=10;
}
pour(len,i,j);
}
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(img[i][j]==1) printf("*");
else if(img[i][j]==0) printf(".");
else printf("x");
}
if(i!=n-1) printf("\n");
}
}

void img_to_code(int n) {
ans.erase(ans.begin(),ans.end());

char c;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
cin >> c;
img[i][j]=c-48;
}
}

divide(0, n, 0,0);
sort(ans.begin(),ans.end());
for(uint i=0; i<ans.size(); i++) {
if(i%12==0&&i!=0) printf("\n");
if(i!=(ans.size()-1) && (i%12!=11)) printf("%d ",ans[i]);
else printf("%d",ans[i]);
}
if(ans.size()!=0) printf("\n");
printf("Total number of black nodes = %d\n", ans.size());
}

void divide(int code,int len, int i, int j) {
if(pure(len,i,j)==1) {
if(img[i][j]==1) {
ans.push_back(five_to_ten(rev(code)));
}
return;
}
divide(code*10+SE,len/2,i+len/2,j+len/2);
divide(code*10+SW,len/2,i+len/2,j);
divide(code*10+NE,len/2,i,j+len/2);
divide(code*10+NW,len/2,i,j);
}

bool pure(int len, int i, int j) {
bool first=img[i][j];
for(int m=i; m<len+i; m++) {
for(int n=j; n<len+j; n++) {
if(img[m][n]!=first) return false;
}
}
return true;
}

void pour(int len, int i, int j) {
for(int m=i; m<len+i; m++) {
for(int n=j; n<len+j; n++) {
img[m][n]=1;
}
}
}

int rev(int code) {
int temp=0;
while(code/10!=0) {
temp=temp+(code%10);
temp*=10;
code/=10;
}
temp+=code;
return temp;
}

int five_to_ten(int num) {
int temp=0;
int power=0;
while(num/10!=0) {
temp+=((num%10)*pow(5,power));
power++;
num/=10;
}
temp+=((num%10)*pow(5,power));
return temp;
}

int ten_to_five(int num) {
int lastbit;
int out=0;
lastbit = num%5;
if(num/5>0) {
out = ten_to_five(num/5);
}
out = out*10+lastbit;
return out;
}
``````

iceman126
New poster
Posts: 5
Joined: Tue Feb 07, 2012 9:13 pm

### Re: 806 - Spatial Structures

Be careful not to output a additional newline when the number of nodes can be divided by 12.

i.e. # of nodes = 12, 24, 36, ...