洛谷 P1498 南蛮图腾

题目描述

自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？

输入输出格式

输入格式：

每个数据一个数字，表示图腾的大小（此大小非彼大小） n<=10

输出格式：

这个大小的图腾

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

   /
  /__
 /  /
/__/__

输入样例#2： 复制

输出样例#2： 复制

       /
      /__
     /  /
    /__/__
   /      /
  /__    /__
 /  /  /  /
/__/__/__/__


这个题由于明显是分形，想到分治。
因为肯定不会超时，所以只要算好每一个小三角形的位置，递归填充就好。
由于换行的问题，最好还是离线处理。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 using namespace std;
 6 int n,m,a[1050][1050];
 7 char s1[]={' ',47,92,' ',''},s2[]={47,'_','_',92,''};
 8 void print(int x,int y,int num)
 9 {
10     int sz=pow(2,num-1);
11     if(num==1)
12     {
13         a[x][y+1]=a[x+1][y]=1;
14         a[x][y+2]=a[x+1][y+3]=2;
15         a[x+1][y+1]=a[x+1][y+2]=3;
16         return ;
17     }
18     print(x,y+sz,num-1);
19     print(x+sz,y,num-1);
20     print(x+sz,y+2*sz,num-1);
21 }
22 int main()
23 {
24     memset(a,0,sizeof(a));
25     scanf("%d",&n);
26     m=pow(2,n);
27     print(1,1,n);
28     for(int i=1;i<=m;i++)
29     {
30         for(int j=1;j<=2*m;j++)
31         {
32             if(a[i][j]==1)
33                 printf("%c",47);
34             else if(a[i][j]==2)
35                 printf("%c",92);
36             else if(a[i][j]==3)
37                 printf("_");
38             else
39                 printf(" ");
40         }
41         printf("
");
42     }
43     return 0;
44 }