| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1131
Chinese Paper Cutting
Time Limit: 2000ms
Memory Limit: 65536kb Description
“Paper cutting is the art of cutting paper designs. ”“Chinese Paper Cutting or Jianzhi is the first type of papercutting design, since paper was invented by Cai Lun in the Eastern Han Dynasty in China. The art form later spread to other parts of the world with different regions adopting their own cultural styles. Because the cut outs are also used to decorate doors and windows, they are sometimes referred to "chuāng huā", meaning Window Flower.” --WikiPedia Alice is a fan of interesting Chinese paper cutting (ICPC). When she first saw it in her grandmother’s house, she immediately fell in love with this art. And from then on, she began to collect various paper cutting designs and tried to create her own works as well. At first, she couldn’t manipulate her scissors and often cut inappropriate parts. Sometimes, she even hurt herself. She had many beautiful designs in her mind, but she was unable to realize them. She was so disappointed for that. However, she didn’t give up. She persisted in practicing, learning from books and experts. At last, she found a key feature of paper cutting. That is symmetry. Symmetry is very important for paper cutting. It not only beautifies the whole work but also makes the cutting process easy. Therefore, cutting each part of a work independently is not a good choice. Instead, it will be better to fold and cut alternately. Now Alice is experienced and works out a paper cutting process which is safe and easy. So she invents a machine that can perform paper cutting following her instructions. This machine has a wide foldable board and a coordinate system on the board. Before the machine runs, she puts a piece of rectangular paper on the board. Two edges of the paper accord with X-axis and y-axis respectively. X-axis is from left to right and y-axis is from top down. Then she starts up the machine and performs a paper cutting process by repeating two types of instructions: fold A B: To execute this instruction, the part of the board containing the point A will be folded onto the other part. So the point A will coincide with B after folding. Then, the folded part will come back to the original position.  Figure 1 As showed in figure 1, Sa is folded onto Sb to make A and B coincide, meanwhile, the paper is folded along the line l . Then, Sa is put back to the original position. But the folded area of the paper is left on Sb. In some cases, the paper may be completely within Sa. If so, the whole paper will be reversed and left on Sb. In contrast, the paper will be unchanged if it is completely within Sb. The folding is limited to be vertical or horizontal. cut n A0 A1 ... An-1 The machine is equipped with a small sharp knife. First, it will use the knife to cut the paper along the line segment A0A1. If there are multiple layers under A0A1, it will penetrate all of them. After that, it will continue to cut along the segment A1A2and then A2A3, etc. Ai can be outside the paper. The machine will cut nothing if it finds the knife is outside the paper. Sometimes it may happen to cut along the joining line of two layers. The knife is so sharp that it will cut off them all the same.  Figure 2 If the paper is divided to several pieces after cutting, the machine will automatically get rid of all pieces but the one with the largest area (after unfolding). If there is a tie, it will keep the one containing the most top-left point in the original paper, i.e. the most left point in the most top horizontal line. Finally, she unfolds the paper and sees a fantastic design. For some complex designs, she is not sure whether her instructions will exactly make what she wants. She doesn’t want to waste paper. So she needs you to write a program that can simulate her instructions and tell her the final design. Given her instructions, your job is to print the final design. Input
The first number indicates the number of test cases. It will not exceed 50.For each test case, the first line contains two integers L, W (0<L, W<=100) indicating the length and width of the paper. The top left corner of the paper is at (0, 0). The second line is a single number T indicating how many instructions she will execute. (0<= T <= 100) The following T lines each are an instruction: cut n x'0 y'0 x'1 y'1 ... x'n-1 y'n-1 Or fold x0 y0 x1 y1 Here (x0, y0), (x1, y1) are the two points which should be in the same place after folding. You can assume that they are distinct and locate in the same vertical or horizontal line. (x'0, y'0), (x'1, y'1) ... (x'n-1, y'n-1) indicates the knife’s path. All the segments are veridical or horizontal. Output
The output of each case should consist of W rows. Each row includes L characters. If the area of [j-1,j]*[i-1,i] remains in the final design, you should print a ‘@’ for the j-th character of the i-th row; Otherwise, print a ‘.’Output an empty line at the end for each test case. Sample Input
3 3 3 3 fold 0 3 0 0 fold 3 0 0 0 cut 3 0 1 1 1 1 0 4 3 3 fold 4 0 0 0 cut 2 2 0 2 3 cut 4 2 1 1 1 1 2 2 2 12 14 8 fold 12 0 0 0 fold 0 14 0 5 fold 0 9 0 4 fold 0 0 0 5 fold 0 3 0 4 fold 0 0 5 0 cut 3 0 6 4 6 4 10 cut 5 6 4 3 4 3 5 5 5 5 10 Sample Output
.@. @@@ .@. @@.. @... @@.. ..@......@.. @@@@@@@@@@@@ ..@......@.. @@@@@@@@@@@@ ..@......@.. @@@@@..@@@@@ @...@..@...@ @@@@@..@@@@@ ..@......@.. @@@@@@@@@@@@ ..@......@.. @@@@@..@@@@@ @...@..@...@ @@@@@..@@@@@ |