蛇形方阵

题目简述

• 给定正整数 $n$，构造一个 $n \times n$ 的方阵。
• 从左上角开始，按顺时针方向填入数字 $1$ 到 $n^2$。
• 输出格式要求：每个数字占 $3$ 个字符宽，左侧空格补齐。

---

关键点分析

1. 填充顺序：
   按顺时针方向填充，即依次为右、下、左、上四个方向循环。

2. 边界判断：
   当下一步位置越界或者该位置已被填充时，需要改变方向。

3. 矩阵状态维护：
   维护一个二维数组 a 用来存放填入的数字，初始化为 $0$ 表示未填。

4. 初始条件：
   起点为 (1, 1)，初始方向向右。

---

实现步骤

• 初始化矩阵大小为 $n \times n$，所有元素为 $0$。
• 设置方向数组 dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}，分别代表右、下、左、上的变化量。
• 设当前坐标 (x, y) = (1, 1)，当前方向 dir = 0。
• 依次填入数字 num 从 $1$ 到 $n^2$。
  • 填入 a[x][y] = num
  • 计算下一步坐标 (nx, ny) = (x + dirs[d][0], y + dirs[d][1])
  • 如果 (nx, ny) 越界（nx < 1 || nx > n || ny < 1 || ny > n）或 a[nx][ny] != 0，说明需换方向：
  • d = (d + 1) % 4
  • 重新计算 (nx, ny)。
• 更新当前坐标为 (nx, ny)。
• 填充完成后，格式化输出矩阵：
  • 每个数字右对齐，占 $3$ 个字符宽，用空格补齐。
  • 数字之间以空格分隔，每行换行。

---

示例代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[15][15];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

signed main()
{
    cin >> n;
    int x = 1, y = 1, dir = 0;
    for (int num = 1; num <= n * n; num++)
    {
        a[x][y] = num;
        if (num == n * n) // 填了最后一个就结束避免继续无限循环下去
        {
            break;
        }
        int nx = x + dx[dir], ny = y + dy[dir];
        // 无法填充
        while (nx < 1 || nx > n || ny < 1 || ny > n || a[nx][ny] != 0)
        {
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        x = nx;
        y = ny;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << setw(3) << a[i][j];
        }
        cout << "\n";
    }
    return 0;
}

---

复杂度分析

• 时间复杂度：$O(n^2)$，每个格子填一次。
• 空间复杂度：$O(n^2)$，用于存储矩阵。

---

总结

• 本题是典型的顺时针螺旋矩阵填充问题。
• 核心在于正确判断边界与已填位置，灵活转向。
• 注意输出格式，数字占3字符宽，左侧补空格。