题目描述

输入两个整数 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

算法: 模拟

时间复杂度 : $O(nm)$

每个格子只会被走到一次,所以时间和棋盘大小成线性

C++ 代码

#include <iostream>

using namespace std;

const int N = 110;
int q[N][N];
bool st[N][N];

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
//走的方向 dx[0],dy[0]向右走 dx[1],dy[1]向下走

int main(void) {
    int n, m, idx = 0, cnt = 1;
    cin >> n >> m;
        for (int j = 0, i = 0; ; j += dy[idx], i += dx[idx]) {
            //当触碰到棋盘边界或者此格子已经被走过,需要调转方向.
            if (i < 0 || i >= n || j < 0 || j >= m || st[i][j]) {
                i -= dx[idx];   //回到合法地点 调转方向
                j -= dy[idx];
                idx = (idx + 1) % 4; 
                continue;
            }
            q[i][j] = cnt++;
            st[i][j] = true;
            if (cnt == n * m + 1) break;    //铺满棋盘 跳出
        }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) 
            cout << q[i][j] << " ";
        cout << endl;
    }
    return 0;
}