题解

题目解析

• 输入输出：输入一个奇数 $n$（$n > 1$）；输出一个 $n \times n$ 的字符矩阵，其中菱形的边框用 # 表示，内部和外部用 . 表示。菱形的四个顶点分别位于第一行中间、最后一行中间、第一列中间和最后一列中间。
• 数据范围：$1 \leq n \leq 29$ 且 $n$ 为奇数，规模极小，允许 $O(n^2)$ 的暴力绘制。
• 复杂度要求：时间复杂度 $O(n^2)$，空间复杂度 $O(1)$（不计输出缓冲区）。
• 算法知识点：模拟、坐标几何、曼哈顿距离、直线方程

思路解析

本题本质是在二维网格上绘制菱形边框。由于 $n$ 最大仅为 $29$，直接枚举每个位置 $(i, j)$ 并判断其是否位于菱形的边上即可。下面给出两种等价的判定方法：

方法一：四边直线方程判定（代码一）
将菱形视为四条线段围成的区域，分别对应四条直线：

1. 上边（左上到右上）：$i + j = \text{mid} + 1$
2. 左边（左上到左下）：$i - j = \text{mid} - 1$
3. 右边（右上到右下）：$j - i = \text{mid} - 1$
4. 下边（左下到右下）：$i + j = n + \text{mid}$

其中 $\text{mid} = (n+1)/2$ 为中心行（列）号。若点 $(i,j)$ 满足上述任一方程，则该点在菱形边上。

方法二：曼哈顿距离判定（代码二）
利用几何性质：该菱形是中心在 $(\text{mid}, \text{mid})$ 的旋转正方形，其边界恰好由到中心曼哈顿距离等于 $\text{mid}-1$ 的所有点构成。即满足：

$$|i - \text{mid}| + |j - \text{mid}| = \text{mid} - 1$$

此方法更简洁，且易于理解菱形的几何本质。

完整代码

#include <bits/stdc++.h>
using namespace std;

// 方法一：四边直线方程判定
int main() {
    int n;
    cin >> n;
    int mid = (n + 1) / 2;  // 中心位置（第mid行第mid列）
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 判定是否位于四条边上（使用逻辑或连接四个条件）
            // 上边: i+j = mid+1 | 左边: i-j = mid-1 | 右边: j-i = mid-1 | 下边: i+j = n+mid
            if (i + j == mid + 1 or i - j == mid - 1 or 
                j - i == mid - 1 or i + j == n + mid) {
                cout << "#";
            } else {
                cout << ".";
            }
        }
        cout << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

// 方法二：曼哈顿距离判定（更简洁的几何思路）
int main() {
    int n;
    cin >> n;
    int mid = (n + 1) / 2;  // 中心坐标
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 关键：菱形边界上的点到中心的曼哈顿距离恒为 mid-1
            // 曼哈顿距离 = |行差| + |列差|
            if (abs(i - mid) + abs(j - mid) == mid - 1) {
                cout << "#";
            } else {
                cout << ".";
            }
        }
        cout << endl;
    }
    return 0;
}