KY58 Repeater

KY58 Repeater

提交网址：http://t.cn/E9jcaVb

描述

Harmony is indispensible in our daily life and no one can live without it----may be Facer is the only exception. One day it is rumored that repeat painting will create harmony and then hundreds of people started their endless drawing. Their paintings were based on a small template and a simple method of duplicating. Though Facer can easily imagine the style of the whole picture, but he cannot find the essential harmony. Now you need to help Facer by showing the picture on computer. You will be given a template containing only one kind of character and spaces, and the template shows how the endless picture is created----use the characters as basic elements and put them in the right position to form a bigger template, and then repeat and repeat doing that. Here is an example. # #  #      <-template # # So the Level 1 picture will be # #  # # # Level 2 picture will be # #     # #  #         # # #     # #      # #         #         # #   # #    # #  #        # # #    # #

你会得到一个只包含一种字符和空格的模板，该模板显示了无尽的图片是如何创建的----使用字符作为基本元素，并将它们放在正确的位置形成一个更大的模板，然后重复做这个 *** 作。 

输入描述：

The input contains multiple test cases. The first 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 N lines describe the template. The following line contains an integer Q, which is the Scale Level of the picture. Input is ended with a case of N=0. It is guaranteed that the size of one picture will not exceed 3000*3000.

输入包含多个测试用例。每种情况的第一行是一个整数N，表示模板的大小是N*N (N只能是3、4或5)，接下来的N行描述模板。下一行包含一个整数Q，它是图片的缩放级别。输入以N=0的情况结束。保证一张图片的尺寸不超过3000*3000。 

输出描述：

For each test case, just print the Level Q picture by using the given template.

 对于每个测试用例，只需使用给定的模板打印Q级别的图片。

示例1

输入：

3
# #
 # 
# #
1
3
# #
 # 
# #
3
4
 OO 
O  O
O  O
 OO 
2
0

输出：

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

思路

输入包含多个测试用例，N=0结束。C++可以这样实现：

int N = 0;
while(cin >> N){
    if(N == 0) break;
    ......
}

输入的模板中有空格，若使用cin接收输入则会剃掉空格，所以需采用cin.get()。（C++ cin.get用法（详解版））

char** unit = new char*[N];//储存基础图形

cin.get();//把输入缓冲区中的n剃掉

for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
        cin.get(unit[i][j]);//读取单个字符，遇n EOF结束
    }
    cin.get();//把输入缓冲区中的n剃掉
}

正式思考解题思路：

以第二个输入为例，

3
# #
 # 
# #
3

把放缩过程想象成一层层“映射”的过程，下面我把基础模板形状抽象为一个X，上一层非空字符映射到下一层变成一个完整模板，空格映射成一个同样大小的“空白”：

经过层层映射到最底层得到最终结果，可以采用递归模拟，第一层放缩规模Q=3，递归往下一层Q减一，直到最后Q==0递归终止，兑现字符。

给定放缩规模Q与模板边长N可以计算结果矩阵边长N^Q，如此先创建一个空白的结果矩阵。在每次递归的时候，根据上一层传下来的上一层对应元素的坐标(row, col)，结合映射的模板中的每一个元素的坐标(i, j)，计算得出本层每个元素的坐标(N*row+i, N*col+j)，传给下一层。递归过程中，可以用一个变量is标识元素是否为非空字符，只有在映射过程中每一层相应元素都是非空字符（is == 1），最终结果的相应位置才是非空字符，否则都是空格。

递归函数思路：

void recur( 放缩等级s, 上一层元素坐标(row, col), 结果矩阵&res, 模板矩阵u ){
    //递归终止条件，递归到第0层
    if(s == 0){
        //上一层为结果矩阵，(row,col)及对应元素为最终结果的坐标与元素;
        给结果矩阵res[row][col]赋相应的值，空格或非空字符;
        return ;
    }

    //继续递归，上一层一个元素映射到本层的一个模板矩阵u
    遍历模板矩阵u，对u中每一个元素u[i][j]：
        执行recur(s-1, 该元素在本层坐标(row*N+i, col*N+j), &res, u);

}

代码

#include
using namespace std;

//递归
void recur(int s, int row, int col, int is, int N, char** u, char** &res, char d){
    //终止条件
    if(s == 0){
        if(is == 1){//此处为非空字符
            res[row][col] = d;
        }else{//此处为空格
            res[row][col] = ' ';
        }
        return ;
    }
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++){
            if(u[i][j] != ' ' && is == 1){//下一层还是非空字符
                recur(s-1, N*row+i, N*col+j, 1, N, u, res, d);
            }else{//下一层是空格
                recur(s-1, N*row+i, N*col+j, 0, N, u, res, d);
            }
        }
}

int main(){
    int N = 0;
    while(cin >> N){
        if(N == 0)break;
        cin.get();//把输入缓冲区中的n剃掉
        
        char** unit = new char*[N];//储存基础图形
        for(int i = 0; i < N; i++)
            unit[i] = new char[N];
        char denote = ' ';//基本符号
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin.get(unit[i][j]);
                if(denote == ' ' && unit[i][j] != ' '){
                    denote = unit[i][j];
                }
            }
            cin.get();//把输入缓冲区中的n剃掉
        }
        
        int scale = 0;//规模
        cin >> scale;
        
        int cap = N;//结果矩阵边长
        for(int i = 1; i < scale; i++)
            cap *= N;
        
        char** res = new char*[cap];//结果矩阵
        for(int i = 0; i < cap; i++)
            res[i] = new char[cap];
        
        //递归
        recur(scale, 0, 0, 1, N, unit, res, denote);
        //输出
        for(int i = 0; i < cap; i++){
            for(int j = 0; j < cap; j++)
                cout << res[i][j];
            cout << endl;
        }
        
    }
    return 0;
}