[UVA][模擬] 10016 - Flip-Flop the Squarelotron
| Flip-Flop the Squarelotron |
The Problem
Anita is the baby siter of Baron Von Hauser’ kids, a famous Physics Assistant of ITESM Campus Monterrey Physics department. As such Von Hauser kids have weird toys, all of which Anita has to master to be able to effectively entertain Baron´ Kids.While Anita was cleaning the bathtub she found a new toy. It is extremely weird, and posses a lot of mathematical symmetry, it is a Squarelotron game. She is determined to understand this new toy, otherwise she won´t be able to play with Von Hauser’ kids. However the complexity of such extreme toy makes it dificult to play. That’s why Anita asked the judges of this ITESM Campus Monterrey internal ACM programming contest eliminatory to put this problem, so that answers could be given by the best sttudents of computer science and engineering of this Campus.
A Squarelotron consist basically of a matrix of numbers. However this matrix can be decomposed as squared rings which can rotate independently in 4 diferent ways, Upside-Down, Left-Rigt, through the Main Inverse Diagonal and through the Main Diagonal.
For example Consider the following Squarelotrons.
Squarelotron a) as 2 rings while squarelotron b) has 3.
A Upside-Down Flip of the outmost ring of Squarelotron a) yields:
A Left-Rigth Flip of the 2 ring of squarelotron b) yields:
A Flip through the Main Inverse Diagonal of the second ring of
squarelotron a) yields:
A Flip through the Main Diagonal of the outermost ring of squarelotron
b) yields:
Anita wants you to do a program which performs the following. She will
give you a Squarelotron and your program will perform several of the flips
described earlier for each of the rings of the given Squarelotron. The
output of your program should be the final state of the Squarelotron.
The Input
The first line contains the number M of different cases to process, consisting of blocks of lines.Each of these blocks consist of the following.
The first line of each block contains a number N which describes the order N x N of the Squarelotron.
Following comes N lines of N numbers each, which describes the Squarelotron itself.
Next comes an equal number of lines as number of rings of the Squarelotron. Each of these lines begins with a number T, followed by T numbers C which identifies the move to perform on the ring.
All these numbers are in the following ranges:
0<M<=1000
1<=N<101
0<T<= Number of Rings
1<=C<5
The numbers in the squarelotron are smaller than 2^16.
The Moves are identifies as follows. 1 means Upside-Down Flip, 2 Means
Left-Right Flip, 3 means flip through the Main Diagonal, 4 means
a flip through the Main Inverse Diagonal.
The Output
For each of the M cases, output a a N x N squarelotron at the state it is supposed to be after all the moves. This squarelotron should be N lines with N numbers each. No blank line in between each case should be output.Sample Input
4 3 1 2 3 4 5 6 7 8 9 2 1 2 4 1 2 3 4 4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 6 2 1 2 2 3 4 5 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 2 3 4 2 1 3 4 1 3 2 4 6 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 4 1 2 2 3 1 1
Sample Output
9 8 7 6 5 4 3 2 1 6 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1 7 6 5 4 3 2 8 3 7 7 6 9 4 8 2 1 1 5 9 6 5 4 3 2 1 4 7 1 4 7 1 5 2 8 5 2 2 6 1 3 4 1 3 7 9 6 7 9 4 8 8 5 2 8 5 9 3 6 9 3 6
題目描述：
把一個 N*N 的矩形看成有 N/2 個環，對於每個環進行翻轉操作。
操作有 4 個，上下翻轉，左右翻轉，
Main Diagonal : 是以↖為主軸翻轉
Main Inverse Diagonal：是以↗為主軸進行翻轉。
對於每個環都給定一系列的操作，問最後盤面為何？
題目解法：
推一下四種可能，對於每個操作都做一次模擬。
#include <stdio.h>
#include <algorithm>
using namespace std;
int g[105][105];
void op1(int n, int r) {
int x = r, y = r;
int i, j;
int w = n-r*2;
for(i = y; i < y+w; i++)
swap(g[x][i], g[x+w-1][i]);
for(i = x+1, j = x+w-2; i < j; i++, j--) {
swap(g[i][y], g[j][y]);
swap(g[i][y+w-1], g[j][y+w-1]);
}
}
void op2(int n, int r) {
int x = r, y = r;
int i, j;
int w = n-r*2;
for(i = x; i < x+w; i++)
swap(g[i][y], g[i][y+w-1]);
for(i = y+1, j = y+w-2; i < j; i++, j--) {
swap(g[x][i], g[y][j]);
swap(g[x+w-1][i], g[x+w-1][j]);
}
}
void op3(int n, int r) {
int x = r, y = r;
int i, j;
int w = n-r*2;
for(i = x; i < x+w; i++)
swap(g[i][y], g[x][i]);
for(i = y+1; i < y+w; i++)
swap(g[x+w-1][i], g[i][y+w-1]);
}
void op4(int n, int r) {
int x = r, y = r;
int i, j;
int w = n-r*2;
for(i = x, j = w-1; i < x+w; i++, j--)
swap(g[i][y], g[x+w-1][y+j]);
for(i = y+1, j = w-2; i < y+w; i++, j--)
swap(g[x][i], g[x+j][y+w-1]);
}
int main() {
int testcase, n;
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &g[i][j]);
int r = n/2, T, C;
if(n%2 == 0) r--;
for(i = 0; i <= r; i++) {
scanf("%d", &T);
while(T--) {
scanf("%d", &C);
if(C == 1)
op1(n, i);
if(C == 2)
op2(n, i);
if(C == 3)
op3(n, i);
if(C == 4)
op4(n, i);
}
}
for(i = 0; i < n; i++, puts("")) {
for(j = 0; j < n; j++) {
if(j) putchar(' ');
printf("%d", g[i][j]);
}
}
}
return 0;
}
/*
4
3
1 2 3
4 5 6
7 8 9
2 1 2
4 1 2 3 4
*/