题目描述

1. 蛇形矩阵
   输入两个整数 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

(dfs)

写这篇题解其实是想让广大懂算法的优秀人士帮本蒟蒻新手提提意见，而且好像很多大佬都是模拟做的吧，不是比dfs快多了（QAQ）

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int m, n;
int num = 1;
int a[1000][1000];

void dfs(int x, int y,int lastdx,int lastdy)
{
    for (int i = 0; i < 4; i++)
    {
        int tx = x + lastdx;
        int ty = y + lastdy;
        if (tx >= n || tx < 0 || ty >= m || ty < 0 || a[tx][ty] != 0)
        {
            if (lastdx == 0 && lastdy == 1)
            {
                lastdx = 1;
                lastdy = 0;
            }
            else if (lastdx == 1 && lastdy == 0)
            {
                lastdx = 0;
                lastdy = -1;
            }
            else if (lastdx == 0 && lastdy == -1)
            {
                lastdx = -1;
                lastdy = 0;
            }
            else if (lastdx == -1 && lastdy == 0)
            {
                lastdx = 0;
                lastdy = 1;
            }
            continue;
        }
        a[tx][ty] = ++num;
        dfs(tx, ty, lastdx, lastdy);
    }
}
int main()
{
    cin >> n >> m;
    a[0][0] = num;
    dfs(0, 0, 0, 1);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }

}