806 - Spatial Structures

[Yaron Wittenstein]

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
i read the input!
please try to help me here!!!!!!!!!!!!!!!!!

[guayoyo]

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

Thanks.

[carlke]

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]

There is nothing wrong with this code.

[carlke]

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]

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, ...