233-2

756. 蛇形矩阵 (偏移量应用)

原题链接 描述：输入两个整数 n 和 m，输出一个 n 行 m 列的矩阵，将数字 1 到 n×m 按照蛇形填充至矩阵中。

具体矩阵形式可参考样例。

输入格式
输入共一行，包含两个整数 n 和 m。

输出格式
输出满足要求的矩阵。
矩阵占 n 行，每行包含 m 个空格隔开的整数。

数据范围
1 ≤ n, m ≤ 100

输入样例：

3 3

输出样例：

1 2 3
8 9 4
7 6 5

分析：

• 创建一个二维数组，用于存放答案。
• 遍历数组，进行判断，在相应位置按递增填入。

判断方法：
1. 可以使用四个if else判断边界
2. 记录偏移量进行判断：

• 设当前位置坐标为 (x, y)，方向：右、下、左、上分别对应 dr = 1, 2, 3, 0（与代码实现一致）。
• 偏移量数组定义为 dx[] = {-1, 0, 1, 0}，dy[] = {0, 1, 0, -1}，分别对应上、右、下、左四个方向的坐标增量。
• 将方向与偏移量的对应关系初始化为两个数组便于引用。
• 
• 每次执行循环后，判断下一个位置是否越界，或该位置已被填充。
• 若满足上述情况，则顺时针改变方向（dr = (dr + 1) % 4）。

代码

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

const int MAXN = 110;

int a[MAXN][MAXN]; // 二维数组
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; // 方向偏移量

int main()
{
    int n, m;
    cin >> n >> m;
    int dr = 1, x = 0, y = 0; // 开始方向为右，起点 (0, 0)
    for (int i = 1; i <= n * m; i++) {
        a[x][y] = i;
        int h = x + dx[dr], l = y + dy[dr];
        if (h < 0 || l < 0 || h >= n || l >= m || a[h][l]) {
            dr = (dr + 1) % 4;
            h = x + dx[dr], l = y + dy[dr];
        }
        x = h, y = l;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

扩展

AcWing 3208. Z字形扫描

原题链接 描述 在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。

给定一个 n×n 的矩阵，Z字形扫描的过程如下图所示：

对于下面的 4×4 的矩阵，

1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

对其进行Z字形扫描后得到长度为 16 的序列：1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3。

请实现一个Z字形扫描的程序，给定一个 n×n 的矩阵，输出对这个矩阵进行Z字形扫描的结果。

输入格式 输入的第一行包含一个整数 n，表示矩阵的大小。 输入的第二行到第 n+1 行每行包含 n 个正整数，由空格分隔，表示给定的矩阵。

输出格式 输出一行，包含 n×n 个整数，由空格分隔，表示输入的矩阵经过Z字形扫描后的结果。

数据范围 1 ≤ n ≤ 500，矩阵元素为不超过 1000 的正整数。

输入样例：

4
1 5 3 9
3 7 5 6
9 4 6 4
7 3 1 3

输出样例：

1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3

分析

• 该题按Z字形遍历数组，对于奇数和偶数情况下，边界转向复杂。
  • 扩大原二维数组，使边界转向统一。
  • 
  • 观察旋转方向，设初始方向 dr = 0。
  • 扩大二维数组，遍历满足在原数组范围内时输出。
  • 

代码

#include <bits/stdc++.h>
using namespace std;
const int N=505;

int a[2*N][2*N]; //定义时直接扩大
int main() {
    int n;
    scanf("%d", &n);
    // 注意：实际应声明足够大的数组，此处为示例简化
    for (int i = 0; i < n; i++) { // 读取二维数组
        for (int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    int dr = 0, dx[] = {0, 1, 1, -1}, dy[] = {1, -1, 0, 1}; // 定义方向偏移量：(0,1)对应dr=0
    printf("%d ", a[0][0]); // 先将(0,0)位置的数输出
    int x = 0, y = 1; // 初始化位置为(0,1)
    for (int i = 0; i < (2 * n - 1); i++) { // 循环遍历对角线，总数应为2n-1条
        for (int j = 0; j < n; j++) { // 在每条对角线上遍历
            if (x >= 0 && x < n && y >= 0 && y < n) {
                printf("%d ", a[x][y]); // 在原始数组范围内输出
            }
            int next_x = x + dx[dr], next_y = y + dy[dr]; // 计算下一个坐标
            if (dr == 0 || dr == 2 || next_y < 0 || next_x < 0 || next_y >= n || next_x >= n) {
                // 如果方向为0或2，或下一个位置越界，则改变方向
                dr = (dr + 1) % 4;
                next_x = x + dx[dr];
                next_y = y + dy[dr];
            }
            x = next_x;
            y = next_y; // 更新位置
            // 按对角线移动时，当一条对角线走完，应跳出内层循环开始下一条对角线
            if (x == 0 || y == n - 1 || x == n - 1 || y == 0) {
                break; // 简化逻辑，实际遍历逻辑可能需要更复杂控制
            }
        }
        // 根据当前位置和方向，初始化下一条对角线的起点
        if (i < n - 1) {
            if (i % 2 == 0) {
                x = i + 1;
                y = 0;
                dr = 0;
            } else {
                x = 0;
                y = i + 1;
                dr = 2;
            }
        } else {
            if (i % 2 == 0) {
                x = n - 1;
                y = i - n + 2;
                dr = 3;
            } else {
                x = i - n + 2;
                y = n - 1;
                dr = 1;
            }
        }
    }
    return 0;
}