©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>蛇形矩阵这道算法题大家应该都遇到过，对于大部分初学者来说是一个比较难的题（包括博主），今天来分享一下解决这道题的简单算法(认真看就一定能看懂！！！)
<>首先我们来分析一下这道题目：
<>思路：
这样的矩阵我们称为蛇形矩阵
<>数字在矩阵中填充的顺序像一条蛇一样，我们可以模拟数字填充的方法，
我们都玩过贪吃蛇小游戏，只不过我们这条贪吃蛇足够聪明，有固定的起点，而且遇到边界会自动调整方向（按顺时针方向旋转）并且不会吃到自己的身体，它可以在给定区域内形成最大长度（身体不允许重叠的情况下）
，以上图为例我们的起点为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.要填充数字的位置未填充过数字.
<>相信仔细思考后你一定理解了这段代码，并对矩阵问题有了更深刻的理解，可以利用上述代码改变方向的方式高效地做出类似算法题。快去刷题吧！