题目描述

输入两个整数n和m，输出一个n行m列的矩阵，将数字 1 到 n*m 按照回字蛇形填充至矩阵中。

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

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

输出格式
输出满足要求的矩阵。

矩阵占n行，每行包含m个空格隔开的整数。

数据范围
1≤n,m≤100

算法1

(DFS) $O(n^2)$

只需要设置一个dx,dy来表示没一次移动的增量，首先没遇到边界，我们就按照设定好的增量去移动，如果遇到边界的时候，通过改变dx,dy来修改应该跳往哪一个移动的位置，这里用dfs来实现。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(register int i=0;i<n;++i)
int dx,dy,n,m,arr[1000][1000],isSearch=0;
void dfs(int x,int y,int n,int m,int idx){
    if(isSearch||arr[y][x]||y>=n||x>=m||y<0||x<0){
        if(dx==1)dx=0,dy=1;
        else if(dx==-1)dx=0,dy=-1;
        else if(dy==1)dx=-1,dy=0;
        else if(dy==-1)dx=1,dy=0;
        return ;
    }
    if(idx==n*m)isSearch=1;
    arr[y][x]=idx;
    dfs(x+dx,y+dy,n,m,idx+1);
    dfs(x+dx,y+dy,n,m,idx+1);
}
int main(){
    cin>>n>>m;
    dx=1,dy=0;
    dfs(0,0,n,m,1);
    FOR(i,n){
        FOR(j,m)cout<<arr[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}