偏移量的应用-acwing的蛇形矩阵和Z字形扫描

题目链接：756. 蛇形矩阵 - AcWing题库

• 设当前位置坐标为(x,y)，上、下、左、右方向分别为dr=0 dr=2 dr=3 dr=1

• 则该位置上、下、左、右的位置所对应的偏移量分别为(x-1,y) (x+1,y) (x,y-1) (x,y+1)

将方向与偏移量的对应关系初始化为两个数组便于引用，每次执行循环后，判断下一个位置是否到达数组边界，或数组中已经存在元素若满足上述情况，则改变方向。

#include <iostream>
using namespace std;

const int N = 110;
int n, m, res[N][N];

int main()
{
    //(0, 1), (1, 0), (0, -1), (-1, 0);
    cin >> n >> m;
    const int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };
    
    //d指四个方向，0 1 2 3，左下右上
    for(int x = 0, y = 0, k = 1, d = 0; k <= n*m; k++)
    {
        res[x][y] = k;
        //下一个位置坐标
        int a = x + dx[d], b = y + dy[d];
        if(a < 0 || a >= n || b < 0 || b >= m || res[a][b] != 0)
        {
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++) cout << res[i][j] << " ";
        cout << endl;
    }
    
    return 0;
}

题目链接：3208. Z字形扫描 - AcWing题库

依次有四种方向【向右/向左下/向下/向右上】，其中向右和向下每次走一步就要转变方向，而向左下和向右上都是走到越界才转向。直到走完n×n 个数停止。注意走过的位置不能再走，由于矩阵元素都是正数，所以可以在走完每一步后将对应的元素置0用于标记已经走过。

#include <iostream>
using namespace std;

const int N = 510;
int n, res[N][N];

int main()
{
    scanf("%d\n", &n);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) scanf("%d", &res[i][j]);
    }
    
    //Z字形扫描的四个方向：
    //向右（0，1），向左下（1， -1）， 向下（1， 0）， 向右上（-1， 1）
    const int dx[] = { 0, 1, 1, -1 }, dy[] = { 1, -1, 0, 1 };
    cout << res[0][0] << " ";
    
    for(int x = 0, y = 0, k = 1, d = 0; k < n * n;)
    {
        //下一个坐标
        int a = x + dx[d], b = y + dy[d];
        if(res[a][b] != 0 && a >= 0 && a < n && b >= 0 && b < n)
        {
            x = a, y = b;
            cout << res[x][y] << " ";
            res[x][y] = 0;
            k++;
            
            if(d == 0 || d == 2) ++d;
        }
        else d = (d + 1) % 4;    // 越界，改变方向 
    }
    return 0;
}