Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

第一回一次性AC……递归232K,16MS,发帖纪念下~~附代码

Posted by vanbreaker at 2013-03-17 20:47:02 on Problem 2083
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator