学步园

传送门 Fractal

还记得这道题是入队第一周的比赛题~~~当时怎么也切不出来~~当时自己还敲了一遍雄哥的代码~~还是不懂

今天仔细一想 分治加递归的思想 果然解决了这道困扰自己很久的题 很有意思

原文是这样的

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X

这就是递归加分治的思想啊

样例一简单

样例二就是往四周加上X

样例3是以样例2为基本单元 

往外扩展的~~说白了就是由5个样例2组成的

post code ：

wa了两次 （1）注意字符数组的范围开大些 （2）由后到前去空格时 注意要用printf("%s",a[i]);输出 若是单个字符的输出会超时~

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
char a[800][800];
int fun(int x,int y,int n){
    if(n==2){                   //以样例二的图形为基本单元
        a[x][y]='X';
        a[x+1][y+1]='X';
        a[x-1][y-1]='X';
        a[x+1][y-1]='X';
        a[x-1][y+1]='X';
        return 1;        
    }    
    int add=(int)(pow(3,n-2)+0.01);   //确定每次偏移的位置
    fun(x,y,n-1);          //递归的思想
    fun(x+add,y+add,n-1);
    fun(x-add,y-add,n-1);
    fun(x+add,y-add,n-1);
    fun(x-add,y+add,n-1);
    
}

int main()
{
 //   freopen("a.txt","r",stdin);
 //   freopen("b.txt","w",stdout);
    int n;
    while(scanf("%d",&n)&&(n!=-1)){
         int pos=(int)(pow(3,n-1)+0.01);
         memset(a,' ',sizeof(char)*(pos+10)*820);
         int x=pos/2,y=pos/2;         //确定中心X的位置
         if(n==1){
           printf("X\n");
           printf("-\n");
           continue;
         }
         fun(x,y,n);
         for(int i=0;i<pos;i++){
             int len=pos+10;
             while(a[i][len]==' '){
              len--;                
             }
             a[i][len+1]='\0';
             printf("%s\n",a[i]);          
                 
         }
         printf("-\n");
                                         
    }
}