解题思路

回形方阵长什么样？

拿 n=5 举例，方阵长这样：

1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1

最外面一圈全是 1，往里一层全是 2，最中间是 3。就像一圈一圈的“回”字。

一个神奇的规律

如果把行、列都用 0 开始编号（第一行是第 0 行，第一列是第 0 列），那么每一个格子上的数，恰好等于它到四条边的最短距离再加 1：

• 最外圈离上边距离是 0，所以是 0+1=1；
• 第二圈离最近的那条边距离是 1，所以是 1+1=2；
• 最中心离四条边都是 2，所以是 2+1=3。

怎么算“到四条边的最短距离”？

对于第 i 行第 j 列的格子（都从 0 开始）：

• 到上边的距离：i；
• 到左边的距离：j；
• 到下边的距离：n-1-i；
• 到右边的距离：n-1-j。

取这四个数里的最小值 d，然后输出 d+1 就是这个格子的数。我们用变量 d 依次和四个距离比较，不断取更小值。

这个做法不用开二维数组，读入 n 之后直接两层循环“边算边输出”就行了。

参考代码

// P4505 回形方阵：每个格子的数 = 它到四边最短距离 + 1
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int d = i;                        // 到上边的距离
            if (j < d) d = j;                 // 到左边的距离
            if (n - 1 - i < d) d = n - 1 - i; // 到下边的距离
            if (n - 1 - j < d) d = n - 1 - j; // 到右边的距离
            cout << d + 1 << " ";             // 层号 = 最短距离 + 1
        }
        cout << endl;
    }
    return 0;
}

复杂度分析

设方阵大小是 n×n。

• 时间：两层循环一共要算出 n×n 个格子，每个格子只做几次比较，时间复杂度是 O(n^2)；
• 空间：不需要数组，只用几个变量，空间复杂度是 O(1)。