题目描述
输入两个整数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(n^2)$
看了一下本题的标签是模拟,但是我用的这个方法好像不是模拟不太清楚,虽然也有判断是否越界和重复走过。希望看到的小伙伴能够指出,嘿嘿
然后我又去看了一下视频讲解,发现y总的思路真的挺棒的。也适用于更多的场景,所以我这个方法就仅供参考啦,题解区的小伙伴的解法也很棒,值得学习
刚开始先将起点位置填上1,当填的数小于$n\*m$时继续(因为“走完一圈”判断一次填的数是否小于$n\*m$,走完一圈可能刚好到终点也可能还没到,但这并不影响结果,最后一次内循环cout必定等于n*m,如果条件是等于的话就会陷入死循环,因为下一个位置填了数,cout不会自增,他们是一直相等的情况,可以说这个判断条件挺巧妙的吧)
遍历每一个方向上的点,先判断当前位置是否出界以及该位置上是否填有数字(全局变量数组初始为0,当然也可以用局部变量,看个人喜欢,局部变量记得初始化就是了,可以用memset()函数),因为如果先填数字发现越界再退回来是挺麻烦的。
接着只要写好每一个方向上的判断即可,注意输出格式
时间复杂度 $O(n*m)$
参考文献
【算法竞赛入门经典(第二版)】刘汝佳
C++ 代码
#include<iostream>
using namespace std;
const int N = 110;
int a[N][N];
int n,m;
int main()
{
cin >> n >> m;
int count = 1,row = 0, col = 0;
a[0][0] = 1;
while(count < n * m){
while(col + 1 < m && !a[row][col + 1]) a[row][++ col] = ++count;
while(row + 1 < n && !a[row + 1][col]) a[++ row][col] = ++count;
while(col - 1 >= 0 && !a[row][col - 1]) a[row][-- col] = ++ count;
while(row - 1 >= 0 && !a[row - 1][col]) a[-- row][col] = ++ count;
}
for(int i = 0; i < n; ++ i)
{
for(int j = 0; j < m; ++ j)
{
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}