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
*/
文章定位: