<>蛇形矩阵这道算法题大家应该都遇到过,对于大部分初学者来说是一个比较难的题(包括博主),今天来分享一下解决这道题的简单算法(认真看就一定能看懂!!!)

<>首先我们来分析一下这道题目:

<>思路:

这样的矩阵我们称为蛇形矩阵

<>数字在矩阵中填充的顺序像一条蛇一样,我们可以模拟数字填充的方法,
我们都玩过贪吃蛇小游戏,只不过我们这条贪吃蛇足够聪明,有固定的起点,而且遇到边界会自动调整方向(按顺时针方向旋转)并且不会吃到自己的身体,它可以在给定区域内形成最大长度(身体不允许重叠的情况下)
,以上图为例我们的起点为1,向右走到4后即遇到边界开始向下走,向下遇到边界向左走然后向上走······,此时它走过的地方成为新的边界,按照这种方法就可以完成矩阵的填充。

<>代码如下:
#include<stdio.h> int main() { int m,n; //m行n列的蛇形矩阵 scanf("%d%d",&m,&n); int
dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; //dx和dy数组用于调整方向 int g[110][110] = {0};
//初始化数组元素全为0 int x = 0,y = 0,d = 1; for(int i = 1;i <= m*n;i ++) { g[x][y] = i;
int a= x + dx[d]; //开始时先向右移,所以从d=1开始 int b = y + dy[d]; //a和b记录要移动到的位置 if(a < 0
|| a >= m || b < 0 || b >= n || g[a][b]) //边界处理,如果满足这四种条件中的一种,即越界,需要改变方向。 { d =
(d + 1) % 4; //顺时针改变方向操作 a = x + dx[d]; b = y + dy[d]; } x = a; y = b; } for(
int i= 0;i < m;i ++) //输出蛇形矩阵 { for(int j = 0;j < n;j ++) printf("%d ",g[i][j]);
printf("\n"); } }
时间复杂度:O(m*n)
空间复杂度:O(1)

<>这段代码不好理解的地方就是边界处理和方向调整,开始是向右然后遇到边界d =
(d+1)%4,再由dx[d],dy[d]重新确定移动方向,边界处理的条件就是不能越界,到算法中实现就是

<>1 .要填充数字的位置下标不能小于0.

<>2 . 要填充数字的位置行数必须小于m,列数必须小于n.

<>3.要填充数字的位置未填充过数字.

<>相信仔细思考后你一定理解了这段代码,并对矩阵问题有了更深刻的理解,可以利用上述代码改变方向的方式高效地做出类似算法题。快去刷题吧!

技术
今日推荐
PPT
阅读数 84
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信