AcWing 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

思路分析：

第一种模拟法，同Basic Level 1050 螺旋矩阵
第二种模拟法，利用 left right top bottom 四个变量 来表示 这个矩形的边界
第三种坐标法通过坐标来实现顺时针旋转撞墙有两种可能一种是到达边界另一种是重复。
第三种方法通用，第二种方法好理解，第一中方法不建议。

代码：

模拟一

#include <iostream>

using namespace std;

const int maxn = 110;
int array_1[maxn][maxn], array_2[maxn * maxn];

int main(){
    int n, m, t = 0;
    cin >> n >> m;
    for(int i = 0; i < n * m; i++){
        array_2[i] = i + 1;
    }
    int level = n / 2 + n % 2;
    for(int i = 0; i < level; i++){
        for(int j = i; j < m - i && t < n * m; j++){
            array_1[i][j] = array_2[t++];
        }
        for(int j = i + 1; j < n - i - 1 && t < n * m; j++){
            array_1[j][m - i - 1] = array_2[t++];
        }
        for(int j = m - i - 1; j >= i && t < n * m; j--){
            array_1[n - i - 1][j] = array_2[t++];
        }
        for(int j = n - i - 2; j > i && t < n * m; j--){
            array_1[j][i] = array_2[t++];
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << array_1[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

模拟二

#include <iostream>

using namespace std;

const int maxn = 110;
int array_[maxn][maxn];

int main(){
    int n, m;
    cin >> n >> m;
    int left = 0, right = m - 1, top = 0, bottom = n - 1, cnt = 1;
    while(left <= right && top <= bottom){
        for(int i = left; i <= right; i++){
            array_[top][i] = cnt++;
        }
        for(int i = top + 1; i <= bottom; i++){
            array_[i][right] = cnt++;
        }
        for(int i = right - 1; i >= left && top < bottom; i--){
            array_[bottom][i] = cnt++;
        }
        for(int i = bottom - 1; i > top && left < right; i--){
            array_[i][left] = cnt++;
        }
        left++, right--, top++, bottom--;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << array_[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

坐标法

#include <iostream>

using namespace std;

const int maxn = 110;
int array_[maxn][maxn];

int main(){
    int n, m, x = 0, y = 0, d = 1, dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    cin >> n >> m;
    for(int i = 1; i <= n * m; i++){
        array_[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if(a < 0 || a >= n || b < 0 || b >= m || array_[a][b]){
            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 << array_[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

AcWing题解
题目链接