[原创]POJ 3768 Repeater 较复杂 分形 题目

2016-03-08 14:06:30 Tabris_ 阅读数：1023

博客爬取于2020-06-14 22:44:57
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50826765

本题网址<-点此进入链接

Repeater
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 4187
Accepted: 1114
Description
Harmony is indispensible in our daily lifeand no one can live without it----may be Facer is the only exception. One dayit is rumored that repeat painting will create harmony and then hundreds ofpeople started their endless drawing. Their paintings were based on a smalltemplate and a simple method of duplicating. Though Facer can easily imaginethe style of the whole picture, but he cannot find the essential harmony. Nowyou need to help Facer by showing the picture on computer.
You will be given a template containingonly one kind of character and spaces, and the template shows how the endlesspicture is created----use the characters as basic elements and put them in theright position to form a bigger template, and then repeat and repeat doingthat. Here is an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#  #
 #     <-template
#  #
So the Level 1 picture will be

#  #
 #
#  #
Level 2 picture will be



#  #   ##
 #     #
#  #   ##
   ##
    #
   ##
#  #   ##
 #     #
#  #   ##

Input
The input contains multiple test cases.
Thefirst line of each case is an integer N, representing the size of the template is N*N (N could only be 3, 4 or 5).
Next Nlines describe the template.
Thefollowing line contains an integer Q, which is the Scale Level of the picture.
Inputis ended with a case of N=0.
It isguaranteed that the size of one picture will not exceed 3000*3000.
Output
For each test case, just print the Level Q picture by using the given template.

Sample Input
3
#  #
 #
#  #
1
3
#  #
 #
#  #
3
4
 OO
O  O
O  O
 OO
2
0
Sample Output
#  #
 #
#  #
#  #   ##        ##   ##
 #    #           #     #
#  #   ##        ##   ##
   ##               ##
    #                 #
   ##               ##
#  #   ##        ##   ##
 #    #           #     #
#  #   ##        ##   ##
         ##  ##
          #    #
         ##  ##
            ##
             #
            ##
         ##   ##
          #    #
         ##  ##
#  #   ##        ##   ##
 #    #           #     #
#  #   ##        ##   ##
   ##               ##
    #                 #
   ##               ##
#  #   ##        ##   ##
 #    #           #     #
#  #   ##        ##   ##
     OO OO
    O OO  O
    O OO  O
     OO OO
 OO         OO
O  O       O  O
O  O       O  O
 OO         OO
 OO         OO
O  O       O  O
O  O       O  O
 OO         OO
     OO OO
    O OO  O
    O OO  O
     OO OO

本题就是一个基础的分形问题 ，只不过是在一个自己定义的图形中，再进行分形处理 。
所以我们一定要把最先定义的图形遍历一遍 找到他的基础结构。用一个二维的数组标记出他的最基础构型 ，就可以开始分型了。
稍有不同的是在分形打印的函数中的递归函数需要双层的for循环来遍历标记数组，
其实在遍历标记数组的时候发现比把每个都写出来要容易操作的多（但时间复杂度会变高），当然本题必须采用遍历的操作才可以，因为自己定义的图形，在没有定义的时候，他的结构就是未知的，所以必须遍历。

接下来就是简单的分型操作了相信你在做这道题的时候已经掌握分形的操作了 这里就不在赘述了

PS：如果真的不了解分形的话，可以看看这篇博客。
2014年蓝桥杯第五题 分型问题 判断递归起点稍有不同<-点此进入链接
哈理工OJ 题目格式较本题稍复杂<-点此进入链接

另附解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# include <stdio.h>
# include <string.h>
# include <math.h>
char a[3002][3002];//图形
char asdf;//分形图形中的字符
char b[6];//输入用的
int num,n;
int flag[6][6];//本组数据是标记用的
void dayin(int cur,int x,int y)
{
    if(cur==1)
    {
       a[x][y]=asdf;
       return ;
    }
   int s=pow(n,cur-2);
   for(int i=0; i<n; i++)//这就是遍历标记数组
    {
       for(int j=0; j<n; j++)
       {
           if(flag[i][j]==1)//如果没有运行就不采取操作
                dayin(cur-1,x+i*s,y+j*s);
       }
    }
}
int main()
{
   while(~scanf("%d",&n))
    {
       getchar();
       if(n==0) break;
       memset(a,' ',sizeof(a));
       memset(flag,0,sizeof(flag));

       for(int i=0; i<n; i++)
       {
           gets(b);
           for(int j=0; j<n; j++)//遍历图形 并标记
           {
                if(b[j]!=' ')
                {
                    asdf=b[j];
                    flag[i][j]=1; //标记
                }
           }
       }

       int m;
       scanf("%d",&m);
       int s=pow(n,m);
       dayin(m+1,1,1);
       for(inti=1; i<=s; i++)//这步主要是控制格式
       {
           a[i][s+1]='\0';
           puts(a[i]+1);//切记一定要用puts 并且交G++  否则无限TLE 其实对比输入优化算法 发现对字符串处理函数的耗时是最短了
       }
    }
}