AcWing 756. 蛇形矩阵

115 阅读 0 评论 76 点赞

我是靠谱客的博主和谐鸡翅，这篇文章主要介绍AcWing 756. 蛇形矩阵，现在分享给大家，希望可以做个参考。

AcWing 756. 蛇形矩阵

写在前面：AcWing是由北大一神级人物——“大雪菜” 创办的算法交流社区, 里面除了正常 oj 网站的功能之外, 还提供单人训练、双人匹配、云端操作系统等模式，除此之外不定期举行各种打卡活动，而且可以分享题解和心得，完全可以当成空间来玩。欢迎大家入坑。
点击前往：AcWing

原题链接

题目描述
输入两个整数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

解题思路

首先肯定要找规律
按照题意的想法, 模拟
移动的时候有四个方向
用坐标(x,y)去模拟
首先一直向右走, 遇到边界, 或者已经走过的时候, 就换方向, 执行6
一直向下走, 遇到边界, 或者已经走过的时候, 就换方向, 执行7
一直向左走, 遇到边界, 或者已经走过的时候, 就换方向, 执行8
一直向上走, 遇到边界, 或者已经走过的时候, 就换方向, 执行5
直到矩阵填充完毕

已过代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# include <iostream>
using namespace std;
int main (){
int m,n;cin>>n>>m;
int x=0,y=0;
int dir=1;
int s[101][101]={0};
for (int i=1;i<=m*n;i++){
//循环m*n次, 
s[x][y]=i;
每次都赋值, 然后更新下一个位置的坐标(x,y)
switch(dir){
case 1: if (y+1<m && s[x][y+1]==0) y++;else x++,dir=2;break;
//如果下一个位置没超过边界并且没走过,就向右走,否则换方向,向下走
case 2: if (x+1<n && s[x+1][y]==0) x++;else y--,dir=3;break;
//如果下一个位置没超过边界并且没走过,就向下走,否则换方向,向左走
case 3: if (y-1>=0&& s[x][y-1]==0) y--;else x--,dir=4;break;
//如果下一个位置没超过边界并且没走过,就向左走,否则换方向,向上走
case 4: if (x-1>=0&& s[x-1][y]==0) x--;else y++,dir=1;break;
//如果下一个位置没超过边界并且没走过,就向上走,否则换方向,向右走
}
}
for (int i=0;i<n;i++){
for (int j=0;j<m;j++)
cout<<s[i][j]<<' ';
cout<<endl;
}
}