transformation
Source: ACM Programming Contest
- A square pattern of black and white tiles is transformed into another square. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
90 Degree Rotation: The pattern was rotated to the right 90 degrees.
180 Degree Rotation: The pattern was rotated to the right 180 degrees.
270 Degree Rotation: The pattern was rotated to the right 270 degrees.
Vertical Reflection: The pattern was reflected vertically. (See test case 4)
Combination: The pattern was reflected vertically and then subjected to one of the rotations.
No Change: The original pattern was not changed.
Invalid Transformation: The new pattern was not obtained by any of the above methods.
Input
The input file will consist of a number n (between 1 and 10 inclusive), which is the size of the square, followed by n lines of the original pattern, and then, after a blank line, the n lines of the transformed pattern. A white square will be indicated by a period; and black squares by an X.
Output
The output from your program should be a phrase describing the transformation that changed the original pattern to the new pattern. If more than one transformation is possible, then your program should show the transformation corresponding to the minimal amount of work necessary to convert the original pattern to the new pattern. For the purposes of evaluating the amount of work needed, rotations are considered less work than reflections, and smaller rotations are less work than larger ones.
Note that only the above possibilities should be considered -- there is no such thing as a 360 Rotation, nor is there a horizontal reflection. Also remember that if a single rotation is not sufficient, your program should consider a reflection followed by a rotation.
-
Test Case 1
Input:
5
X...X
.X...
...X.
..X.X
....X
....X
...X.
.X...
..X..
XX..X
Output:
ROTATED 90 DEGREES.
|
Test Case 2
Input:
6
....XX
...X..
XX..X.
..X...
...X..
..X..X
X....X
X.X...
.X..X.
...X.X
..X...
..X...
Output:
ROTATED 270 DEGREES.
|
Test Case 3
Input:
2
X.
.X
X.
.X
Output:
NOT TRANSFORMED.
|
Test Case 4
Input:
4
..X.
XX..
....
...X
...X
....
XX..
..X.
Output
REFLECTED.
|
Test Case 5
Input:
5
X....
.X...
.X...
...X.
....X
.X...
..X..
..X..
....X
X....
Output:
IMPROPER TRANSFORMATION.
|
|
