题解：P14612 [2019 KAIST RUN Fall] 6789

FloydNotCut · 2025-11-27 19:11:32 · 题解

题目大意

给定一个矩阵，满足任取元素 s ∈ { 6, 7, 8, 9 }，判断 180 旋转后是否对称，其中 6 与 9 可通过互相翻转得到，8 翻转后不影响，7 翻转后为倒 7，问至少预先将多少数字翻转后可以保证矩阵中心对称

分析

很明显，这道题模拟即可。

我们需要枚举每个通过旋转 180° 重合的位置。

可以通过以下计算得到：

auto x = n - i + 1;
auto y = m - j + 1;

下面列举模拟的内容：

• 我们知道 6 和 9 通过翻转可以互相得到，8 和本身通过翻转可以互相得到，这些操作是不计代价的，那么可以写出：

if ((a[x][y] == 8 && a[i][j] == 8) || (a[x][y] == 6 && a[i][j] == 9) || (a[x][y] == 9 && a[i][j] == 6) && (x != i || y != j)) continue;

• 我们还能发现 7 由于翻转是无效的，所以一定是要记代价的：

if (a[x][y] == 7 && a[i][j] == 7 && (x != i || y != j)) cnt++;

• 6 和本身或者 9 和本身可以通过一次旋转得到：

if (a[x][y] == 6 && a[i][j] == 6 && (x != i || y != j)) cnt++;
else if (a[x][y] == 9 && a[i][j] == 9 && (x != i || y != j)) cnt++;

• 8 本身可以得到自己，不记代价，需要特判，需要注意的是这里的 8 和上面的 8 不一样，因为这个 8 是指坐标完全一致的 8，哪想一下是哪一种情况呢，当然是整个矩阵的中心啦！

if (a[x][y] == 8 && a[i][j] == 8 && x == i && y == j) continue;

剩下的情况很显然就不可能满足情况了，直接输出 - 1，退出就行了。

下面给出 AC 代码：

AC Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, m;
const int N = 505;
int a[N][N];
int cnt = 0;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j-1] - '0';
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            auto x = n - i + 1;
            auto y = m - j + 1;
            if (a[x][y] == 8 && a[i][j] == 8 && x == i && y == j)
                continue;
            else if (a[x][y] == 6 && a[i][j] == 6 && (x != i || y != j))
                cnt++;
            else if (a[x][y] == 9 && a[i][j] == 9 && (x != i || y != j))
                cnt++;
            else if (a[x][y] == 7 && a[i][j] == 7 && (x != i || y != j))
                cnt++;
            else if ((a[x][y] == 8 && a[i][j] == 8) || (a[x][y] == 6 && a[i][j] == 9) || (a[x][y] == 9 && a[i][j] == 6) && (x != i || y != j))
                continue;
            else
            {
                cout << "-1\n";
                exit(0);
            }
        }
    }

    cout << cnt / 2 << '\n';

    return 0;
}