[原创]POJ3768 较复杂分形题目

2015-12-28 17:14:17 Tabris_ 阅读数：456

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

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

本题就是一个基础的分形问题 ，只不过是在一个自己定义的图形中，再进行分形处理  。

所以我们一定要把最先定义的图形遍历一遍 找到他的基础结构。用一个二维的数组标记出他的最基础构型 ，就可以开始分型了。

稍有不同的是在分形打印的函数中的递归函数需要双层的for循环来遍历标记数组，

其实在遍历标记数组的时候发现比把每个都写出来要容易操作的多（但时间复杂度会变高），当然本题必须采用遍历的操作才可以，因为自己定义的图形，在没有定义的时候，他
的结构就是未知的，所以必须遍历。

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

PS：如果真的不了解分形的话，可以看看这篇博客。

2014年蓝桥杯第五题 分型问题  判断递归起点稍有不同

http://blog.csdn.net/qq_33184171/article/details/50390031

哈理工OJ 题目格式较本题稍复杂

http://blog.csdn.net/qq_33184171/article/details/50274193

本题网址： http://poj.org/problem?id=3768

方便读者  题目放到了本文最后

另附解题代码

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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 至于为什么 我也不知道

       }

    }

}

** 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.

#     <-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

** Source **