USACO 1.2 – Transformations | Jack Neus
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
http://972169909-qq-com.iteye.com/blog/1075958
http://code.antonio081014.com/2012/09/usaco-transformations.html
Read full article from USACO 1.2 – Transformations | Jack Neus
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
- #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
- #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
- #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
- #4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
- #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
- #6: No Change: The original pattern was not changed.
- #7: Invalid Transformation: The new pattern was not obtained by any of the above methods.
INPUT FORMAT
| Line 1: | A single integer, N |
| Line 2..N+1: | N lines of N characters (each either `@' or `-'); this is the square before transformation |
| Line N+2..2*N+1: | N lines of N characters (each either `@' or `-'); this is the square after transformation |
SAMPLE INPUT (file transform.in)
3 @-@ --- @@- @-@ @-- --@
OUTPUT FORMAT
A single line containing the the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation.SAMPLE OUTPUT (file transform.out)
1
string reverse(string s){
string result = "";
for(int i = s.length() - 1; i >= 0; i--){
result += s[i];
}
return result;
}
string reflect(string str, int N){
vector<string> rows(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
rows[i] += str[N * i + j];
}
}
string reflected;
for(int i = 0; i < N; i++){
reflected += reverse(rows[i]);
}
return reflected;
}
string rotate(string orig,int N){
vector<string> col_orig(N);
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
col_orig[i] += orig[N * j + i];
}
}
string rotated = "";
for(int i = 0; i < N; i++){
rotated += reverse(col_orig[i]);
}
return rotated;
}
int main(){
ifstream in("transform.in");
ofstream out("transform.out");
int N;
in >> N;
string orig;
string trans;
for(int i = 0; i < N; i++){
string temp;
in >> temp;
orig += temp;
}
for(int i = 0; i < N; i++){
string temp;
in >> temp;
trans += temp;
}
int trans_id;
if(rotate(orig, N) == trans){ //90 deg
trans_id = 1;
}
else if(rotate(rotate(orig, N), N) == trans){ //180 deg
trans_id = 2;
}
else if(rotate(rotate(rotate(orig, N), N), N) == trans){ //270 deg
trans_id = 3;
}
else if(reflect(orig, N) == trans){
trans_id = 4; //reflection
}
else if(rotate(reflect(orig, N), N) == trans || rotate(rotate(reflect(orig, N), N), N) == trans || rotate(rotate(rotate(reflect(orig, N), N), N), N) == trans){ //combination
trans_id = 5;
}
else if(orig == trans){ //no change
trans_id = 6;
}
else{ //invalid change
trans_id = 7;
}
out << trans_id << endl;
}
http://972169909-qq-com.iteye.com/blog/1075958
http://code.antonio081014.com/2012/09/usaco-transformations.html
Read full article from USACO 1.2 – Transformations | Jack Neus
