题目描述
输入两个整数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
(枚举偏移量进行计算) $O(n*m)$
模拟走路,利用偏移量一步一步走,然后填字;
1.模拟操作,我们观察如何枚举下一步;对于每个下一步,我们只关心x和y,每次先右边走,就是x不变,y加上一;
如果是向下走就是x加1,y不变,如果是向左走就是x不变,y减去一;这样子;
2.判断条件:越界就转弯,下一个碰头就转弯,如果下一个位置有数值的话就转弯;下一个地方已经有数字,不是0了也要转头.
3.每次要先预判,然后能够走的话就走,然后走,继续判断;
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
int a[110][110];
int dirx[4]={0,1,0,-1};//定义x的位置的数组
int diry[4]={1,0,-1,0};//定义y的位置数组
int n,m,x,y;
int main()
{
cin>>n>>m;int x=0,y=0,t=0;
for(int i=1;i<=n*m;++i)
{
a[x][y]=i;//填入这个字
int tx=x+dirx[t];//判断下一个位置的横坐标
int ty=y+diry[t];//判断下一个位置的纵坐标
if(tx<0||ty<0||tx>=n||ty>=m||a[tx][ty]!=0)//判断要不要转弯
{
t=(t+1)%4;//t往下取一位
tx=x+dirx[t];//转弯后往下走一位
ty=y+diry[t];
}
x=tx;
y=ty;//更新当前位置
}
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}