USACO Section 1.2: Transformations
12037 ワード
1 /*
2 ID: leetcod3
3 PROG: transform
4 LANG: C++
5 */
6 #include <iostream>
7 #include <fstream>
8 #include <string>
9 #include <map>
10 #include <vector>
11 #include <set>
12 #include <algorithm>
13 #include <stdio.h>
14 #include <queue>
15 #include <cstring>
16 #include <cmath>
17 #include <list>
18 #include <cstdio>
19 #include <cstdlib>
20 #include <limits>
21 #include <stack>
22
23 using namespace std;
24
25 ofstream fout ("transform.out");
26 ifstream fin ("transform.in");
27
28 bool same(vector<string> &square, vector<string> &output) {
29 for (int i = 0; i < square.size(); i++) {
30 if (square[i] != output[i]) return false;
31 }
32 return true;
33 }
34
35 void rotates(vector<string> &square) {
36 int N = square.size();
37 for (int i = 0; i < N / 2; i++) {
38 for (int j = i; j < N - 1 - i; j++) {
39 int tmp = square[i][j];
40 square[i][j] = square[N-1-j][i];
41 square[N-1-j][i] = square[N-1-i][N-1-j];
42 square[N-1-i][N-1-j] = square[j][N-1-i];
43 square[j][N-1-i] = tmp;
44 }
45 }
46 }
47
48 void reflect(vector<string> &square) {
49 int N = square.size();
50 for (int i = 0; i < N; i++) {
51 for (int j = 0; j < N/2; j++) {
52 swap(square[i][j], square[i][N-j-1]);
53 }
54 }
55 }
56
57 int main() {
58 int N;
59 fin >> N;
60 vector<string> square(N);
61 vector<string> output(N);
62 for (int i = 0; i < N; i++) fin >> square[i];
63 for (int i = 0; i < N; i++) fin >> output[i];
64 int ans = 7;
65 if (same(square, output)) ans = 6;
66 /*for (int i = 0; i < N; i++) {
67 cout << square[i] << endl;
68 }
69 cout << endl;*/
70 rotates(square);
71 /*for (int i = 0; i < N; i++) {
72 cout << square[i] << endl;
73 }
74 cout << endl;*/
75 if (same(square, output)) ans = min(ans, 1);
76 rotates(square);
77 if (same(square, output)) ans = min(ans, 2);
78 rotates(square);
79 if (same(square, output)) ans = min(ans, 3);
80 rotates(square);
81 reflect(square);
82 /*for (int i = 0; i < N; i++) {
83 cout << square[i] << endl;
84 }*/
85 if (same(square, output)) ans = min(ans, 4);
86 for (int i = 0; i < 3; i++) {
87 rotates(square);
88 if (same(square, output)) ans = min(ans, 5);
89 }
90 fout << ans << endl;
91 return 0;
92 }