题目描述

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

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

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//模拟 
//从第一行第一列开始向右走，每走一格，对应数字加1，当走到边界时，改变方向，直到按蛇形走完数组即可。 
#include<iostream>
using namespace std;
#define N 110
int b[N][N];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};        //方向数组 模拟从1开始 先向右 再向下 再向左 再向上 然后循环 
int main()
{
    int n,m;                            
    cin>>n>>m;                              //确定二维数组规模 
    for(int i = 1;i <= n;i++)               //将b数组初始化为-1 用于判断是否出界或已经走过 
       for(int j = 1;j <= m;j++)
            b[i][j]=-1; 
    int x = 1,y = 1,j = 1;                  //j用于赋值，必须放在外边，以防j被重新赋值为1。 
    for(int i = 0;i <= 3;i++)
    {
        for(;j <= n*m;)
        {
            if(b[x][y]==-1)                 //判断是否走过或出界 
            {
                b[x][y]=j;
                j++;                        //j++在这个位置很重要，因为只有符合条件才能赋值，出界或走过不能赋值且不能改变j的值，否则对后边赋值造成影响 
                x=x+dx[i];                  //走下一步 
                y=y+dy[i];
            }
            else
            {
                x=x-dx[i];                  //出界或已经走过则退到上一步 
                y=y-dy[i];
                if(i==3)                    //当i=3时 i+1=4 方向数组无dx[4] 所以此处用于i=3情况的特判 
                    i=-1;
                x=x+dx[i+1];                //改变方向 
                y=y+dy[i+1];
                break;  
            }
        }
        if(i==3)                            //用于方向循环改变 
            i=-1;

        if(j==n*m+1)                        //当n*m+1时候终止，否则最后一个数不会被赋值，这一点想清楚。 
            break;
    }
     for(int i = 1;i <= n;i++)              //输出 
     {
        for(int j = 1;j <= m;j++)
            cout<<b[i][j]<<" ";
        cout<<endl;
    }
        return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla