POJ 3768(分形+递归)

xiaoxiao2021-02-28  37

题目链接:点击打开链接

题目大意:输入一个n表示原始图案的行和列,要求按照原图案的样子进行复制m次,求最后的图像

题目思路:太菜了..看了三个半小时才会...........................主要是不知道这个打印的过程以及如何实现的....我把中途的变量啥的都打出来然后才知道的...........这里详细地讲述一下..................

这分别是第一次复制和第二次复制的图形.......先把左上角这个大的复制完,然后是右上角的,为啥是这样复制的呢....首先先想一下,原图案被放入复制队列的顺序。是从左上角第一个一行行遍历来的,所以被拉近复制大军的顺序是先第一行最左开始,一行行来,复制也是按照这个顺序。

说完了复制顺序,接下来来谈咋实现...其实我们很容易发现,只要找到了其中一个人复制的位置,就能完成了,所以我们的本质,是找到第一个点在他对应的复制的位置的坐标,只要找到了剩下的按照第一个来就好了....

核心代码:dfs(m-1,x+i*size,y+j*size),i和j是每个点对应的坐标,*size就能到达那个对应的地方,这个需要自己多感悟感悟(我感觉其实还是我太菜不能表达..不过认真想想你能搞懂的..)

以下是代码:

#include<iostream> #include<cstdio> #include<math.h> using namespace std; char str[6][6],map[3005][3005]; int n,m; void dfs(int m,int x,int y){ if(m==1){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ map[x+i][y+j]=str[i][j]; } } return; } int size=(int)pow(n*1.0,m-1); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(str[i][j]!=' '){ dfs(m-1,x+i*size,y+j*size); } } } } int main(){ while(~scanf("%d",&n)&&n){ int size; getchar(); for(int i=0;i<n;i++){ gets(str[i]); } scanf("%d",&m); size=(int)pow(n*1.0,m); for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ map[i][j]=' '; } map[i][size]='\0'; } dfs(m,0,0); for(int i=0;i<size;i++){ printf("%s\n",map[i]); } } return 0; }

转载请注明原文地址: https://www.6miu.com/read-2625376.html

最新回复(0)