Elegant Diamond 题解

题意简述

给你一个由数字组成的菱形，问需要最少加多少个数字，才能让这个菱形变成优雅的（整个菱形内的数字满足水平和竖直方向都是对称的）。

思路分析

由题，优雅菱形需要同时满足水平对称和垂直对称，所以可得这个菱形必须关于某个中心点完全对称。

显然，对于任意一个优雅菱形，一定存在一个中心点 \((i, j)\)，能够使得菱形内任意一点 \((x, y)\)，满足 \((x, y)\) 关于中心点 \((i, j)\) 的对称点 \((2i-x, 2j-y)\) 的数字与 \((x, y)\) 相同。

因为这道题的数据范围很小，所以我们可以考虑通过枚举来实现这道题。我们只需要枚举整个菱形的所有可能对称中心，然后计算其水平对称位置 \((x, 2j-y)\) 和垂直对称位置 \((2i-x, y)\)，接着判断其对称位置是否符合条件，如果完全对称则标记为可行中心。对于所有的可行中心，我们只需要找到偏移量最小的那一个就可以了。

那么该如何计算呢？对于每个可行中心 \((i, j)\)：

• 偏移量是 \(dx = |i - (k-1)|,\ dy = |j - (k-1)|\)
• 扩展后大小是 \(k' = k + dx + dy\)
• 需要添加的数字数是 \(m = (k')^2 - k^2\)（菱形数字总数 \(= k^2\)）

然后输出所有可行中心中添加的数字数的最小值就行了。

参考代码

:::success[Accepted!]{open}

#include <bits/stdc++.h>
#define int long long
#define fast_running ios::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int k, n;
string s[200];
signed main() {
	fast_running;
	int T;
	cin >> T;
	for (int Case = 1; Case <= T; Case++) {
		cin >> k;
		n = k * 2 - 1;
		cin.ignore();  // 忽略换行符，防止 getline 去世
		for (int i = 0; i < n; i++) {
			getline(cin, s[i]);
			if (s[i].length() < n) s[i] += string(n - s[i].length(), ' ');
			// 统一字符长度，方便枚举，防 RE
		}
		cout << "Case #" << Case << ": ";
		int m = INT_MAX;
		for (int i = 0; i < n; i++) { // 枚举所有可能得对称中心
			for (int j = 0; j < n; j++) {
				bool flag = true;
				for (int x = 0; x < n && flag; x++) {  // 检查可行性
					for (int y = 0; y < n && flag; y++) {
						if (s[x][y] != ' ') {
							int nx = 2 * i - x;
							int ny = 2 * j - y;
							if (0 <= nx && nx < n) { // 检查垂直对称
								if (s[nx][y] != ' ' && s[nx][y] != s[x][y]) flag = false;
							}
							if (0 <= ny && ny < n) { // 检查水平对称
								if (s[x][ny] != ' ' && s[x][ny] != s[x][y]) flag = false;
							}
						}
					}
				}
				// 如果 (i, j) 是可行中心，计算偏移量
				if (flag) m = min(m, abs(i - k + 1) + abs(j - k + 1));
			}
		}
		cout << (k + m) * (k + m) - k * k << '\n';
	}
	return 0;
}

:::