C:9-9题目:蛇形矩阵

JonlyMay 2024-09-14 09:05:05 阅读 66

一、题目介绍:

给你两个整数n,m,请你构造一个n行m列的蛇形方阵,在这个方阵中,数字由1到n×m,从最右上角开始,呈环状(逆时针)向内填充。

比如一个3*3的蛇形方阵

3 2 1

4 9 8

5 6 7

二、解题思路:

分析题目:

1.该矩阵是一个方阵,填入矩阵内的值是从1开始的;

2.该矩阵的填充顺序是逆时针向内填充的。具体可以参考上面所给的蛇形矩阵。

具体思路:

1. 初始化矩阵

 创建一个  n  行  m  列的全零矩阵,用于存储最终的蛇形方阵。

2. 设置起始位置和初始方向

 将起始位置设置为第一行最后一列,即  row = 0 , col = m - 1 。

 初始方向设为向左(可以用数字表示方向,比如 0 表示向左,1 表示向下,2 表示向右,3 表示向上)。

3. 填充数字

 从数字 1 开始,依次填充到矩阵中。

 根据当前方向尝试填充下一个数字。例如,如果当前方向是向左,就尝试在当前列减一的位置填充下一个数字。

 如果下一个位置已经被填充或者超出了矩阵边界,则改变方向。

4. 改变方向

 按照逆时针方向改变方向。如果当前方向是向左,当无法继续向左填充时,改为向下填充,即方向变为 1。如果是向下,当无法继续向下填充时,改为向右填充,以此类推。

5. 重复填充和改变方向的步骤

 不断重复填充数字和改变方向的步骤,直到所有  n×m  个数字都被填充到矩阵中。

三、逐步代码实现:

<code>int n = 0;

int m = 0;

scanf("%d %d", &n, &m);

int squmat[m][m];

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

squmat[i][j] = 0;

}

}

先初始化n,m,然后键盘输入矩阵行和列,再通过两个for循环将矩阵元素全部填充为0。

变量初始化:

int num = 1;

int row = 0; int col = m - 1;

int change = 0;

这里初始化一些变量,num为输入矩阵的第一个值1, int row = 0; int col = m - 1;使得输入的数字填充在矩阵右上角。

变量change帮助我们实现方向的变化,这里规定一下;

change = 0,1,2,3;填充方向分别是向左,向下,向右,向上。

while循环: 

while (num <= n * m)

{

squmat[row][col] = num;

num++;

}

这里我们通过while循环来将数字填充到矩阵中。

循环条件num <= n * m,当填充的数字大于矩阵内元素总数时结束循环,比如说3*3的矩阵,当我们填充的数字num = 10 的时候,大于3*3 = 9;10不在填入矩阵内。

squmat[row][col] = num;将1的值赋值到矩阵右上角;

num++随着循环变化调整所赋的值。

填入数字详细介绍:

向左填充:

if (change == 0)

{

if (col > 0 && squmat[row][col] == 0)

{

col--;

}

else

{

row++;

change = 1;

}

}

上述代码实现向左填充数字,当满足col > 0 && squmat[row][col] == 0条件时,列数就减一列,这是因为我们是从右上角开始填充的数字,列数起始就是最后一列。

col > 0 && squmat[row][col] == 0解释

由于列数是逐渐递减的,因此当列数小于0的时候,就不满足填充条件了,squmat[row][col] == 0判断填充的下一个位置是否为0,如果不是0就不能填充,不是0的位置说明已经填充过数字了。

如果不满足填充条件,则跳到下一行,这时候我们填充数字的方向就要改变了,由原来的向左填充改为向下填充,change变为1。

squmat[row][col] == 0判断当前位置(由rowcol确定)的元素是否为 0。在螺旋矩阵的填充过程中,只有当该位置的元素为 0 时,才表示该位置还没有被填充过,才可以进行填充操作;如果该位置不为 0,说明已经被填充过了,需要改变填充方向。

图解:

b5df0896b886470295b6e3dbc75237db.jpeg

向下填充:

<code>else if (change == 1)

{

if (row < n - 1 && squmat[row + 1][col] == 0)

{

row++;

}

else

{

col++;

change = 2;

}

}

当满足row < n - 1 && squmat[row + 1][col] == 0时,行数就加1行,向下填充,如果不满足该条件,列数增加,change改为2,开始向右填充。

row < n - 1 && squmat[row + 1][col] == 0解释:

1.row < n - 1

row < n - 1这个条件是判断当前行索引是否小于矩阵总行数减 1,这意味着还没有到达矩阵的最后一行。如果这个条件不满足,说明已经到了最后一行,不能再往下一行进行填充操作。

2.squmat[row + 1][col] == 0

(1)squmat[row + 1][col]表示当前位置的下一行同一列的元素。

(2)squmat[row + 1][col] == 0判断下一行同一列位置的元素是否为 0。如果是 0,则表示该位置还没有被填充数字,可以将数字按螺旋顺序填充到该位置;如果不是 0,则说明该位置已经被填充过,不能再填充,需要改变填充方向。

96b3d78503e94cb586bd0b51430048b4.jpeg

向右填充:

<code>else if (change == 2)

{

if (col < m - 1 && squmat[row][col + 1] == 0)

{

col++;

}

else

{

row--;

change = 3;

}

}

当满足col < m - 1 && squmat[row][col + 1] == 0条件,col就加1,向右填充,如果不满足该条件,行数减1,填入数字方向改为向上填充,change = 3。

col < m - 1 && squmat[row][col + 1] == 0理解:

col < m - 1 部分

col是当前元素在矩阵中的列位置,m是矩阵的列数。col < m - 1这个条件用于判断当前列是否小于矩阵总列数减 1。这是因为在矩阵中,列索引从 0 开始,当col等于m - 1时,已经到达了矩阵最右侧的列,再向右就超出矩阵范围了。

squmat[row][col + 1] == 0部分

squmat[row][col + 1]表示当前元素的右侧相邻元素(在同一行,列索引增加 1)。squmat[row][col + 1] == 0 判断右侧相邻元素的值是否为 0。在蛇形矩阵填充算法中,值为 0 通常表示该位置尚未被填充数字。

向上填充:

else if (change == 3)

{

if (row > 0 && squmat[row - 1][col] == 0)

{

row--;

}

else

{

col--;

change = 0;

}

}

与上类似,就跳过了。

四、完整代码:

#include <stdio.h>

int main()

{

int n = 0;

int m = 0;

scanf("%d %d", &n, &m);

int squmat[m][m];

for (int i = 0; i < n; i++)

{

for (int j = 0; j < m; j++)

{

squmat[i][j] = 0;

}

}

int num = 1;

int row = 0; int col = m - 1;

int change = 0;

while (num <= n * m)

{

squmat[row][col] = num;

num++;

if (change == 0)

{

if (col > 0 && squmat[row][col] == 0)

{

col--;

}

else

{

row++;

change = 1;

}

}

else if (change == 1)

{

if (row < n - 1 && squmat[row + 1][col] == 0)

{

row++;

}

else

{

col++;

change = 2;

}

}

else if (change == 2)

{

if (col < m - 1 && squmat[row][col + 1] == 0)

{

col++;

}

else

{

row--;

change = 3;

}

}

else if (change == 3)

{

if (row > 0 && squmat[row - 1][col] == 0)

{

row--;

}

else

{

col--;

change = 0;

}

}

}

for (int i = 0; i < n; i++)

{

for (int j = 0;j < m; j++)

{

printf("%d ", squmat[i][j]);

}

}

return 0;

}

 

 



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。