| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
第一回一次性AC……递归232K,16MS,发帖纪念下~~附代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct X_POS
{
unsigned short row;
unsigned short col;
};
struct X_POS xpos[15625];//the total 'X' is no more than 15625
int size=0;
int level(int n)
{
int i,s;
for(i=0,s=1;i<n-1;i++)
s *= 3;
return s;
}
void fractal(int row,int col,int n)
{
int lv;
if(n==1)
{
xpos[size].row = row;
xpos[size].col = col;
size++;
return;
}
lv = level(n-1);
fractal(row, col, n-1);
fractal(row, col+2*lv, n-1);
fractal(row+2*lv, col, n-1);
fractal(row+2*lv, col+2*lv, n-1);
fractal(row+lv, col+lv, n-1);
}
int my_compare(const void *item1, const void *item2)
{
struct X_POS *x1,*x2;
x1 = (struct X_POS*)item1;
x2 = (struct X_POS*)item2;
if(x1->row == x2->row)
return x1->col - x2->col;
return x1->row - x2->row;
}
void output(int n)
{
char str[750];
int i,j;
int lv;
unsigned short col;
lv = level(n);
//input each level into str[] and outputs it one by one.
for(i=0,j=0;i<lv;i++)
{
memset(str,' ',lv);
while(j<size-1 && xpos[j].row == xpos[j+1].row)
{
col = xpos[j].col;
str[col] = 'X';
j++;
}
col = xpos[j++].col;
str[col] = 'X';
str[col+1] = '\0';
printf("%s\n",str);//print a row
}
}
int main(void)
{
int n;
scanf("%d",&n);
while(n!=-1)
{
size = 0;
fractal(0, 0, n);
qsort(xpos, size, sizeof(struct X_POS), my_compare);
output(n);
printf("-\n");
scanf("%d",&n);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator