题目链接:http://codeforces.com/contest/426/problem/B
题目意思:给出一个n * m的矩阵a,需要找出一个最小的矩阵b,它能通过several次的mirrorings变成a。mirrorings的操作是这样的:a的upper half(假设行是1~x)部分等于b,lower half(x+1~n部分与upper half 部分对称。对称线处于 x 和 x+1 之间。
很明显,如果矩阵a的行是奇数的话,是找不出 b 的。偶数的时候就通过比较对称的两部分是否相等来处理。
写这题是为了和参考别人的代码对比。
这是我的:
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int maxn = 100 + 5; 9 int a[maxn][maxn];10 int n, m;11 12 int check(int tn)13 {14 if (tn & 1)15 return 0;16 int flag = 0;17 int half = tn / 2;18 for (int j = 1; j <= m; j++)19 {20 for (int i = 1; i <= half; i++)21 {22 if (a[i][j] != a[tn+1-i][j])23 {24 flag = 1;25 break;26 }27 }28 }29 if (flag)30 return 0;31 return 1;32 }33 34 int main()35 {36 int s, i, j;37 while (scanf("%d%d", &n, &m) != EOF)38 {39 for (i = 1; i <= n; i++)40 {41 for (j = 1; j <= m; j++)42 cin >> a[i][j];43 }44 if (check(n))45 {46 int tn = n / 2;47 while (check(tn))48 {49 tn /= 2;50 check(tn);51 }52 printf("%d\n", tn);53 }54 else55 printf("%d\n", n);56 }57 return 0;58 }
参考别人代码写的:
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef vector vi; 8 typedef vector vii; 9 10 int main()11 {12 int n, m, i, j;13 while (scanf("%d%d", &n, &m) != EOF)14 {15 vii a(n, vi(m));16 for (i = 0; i < n; i++)17 {18 for (j = 0; j < m; j++)19 cin >> a[i][j];20 }21 bool ok = true;22 int tn = n;23 while (true)24 {25 if (tn & 1 || !ok)26 {27 printf("%d\n", tn);28 break;29 }30 tn = n;31 n /= 2;32 for (j = 0; j < m; j++)33 {34 for (i = 0; i < n; i++)35 ok &= a[i][j] == a[tn-i-1][j];36 }37 }38 }39 return 0;40 }