【寒假每日一题】蛇形矩阵

【寒假每日一题】蛇形矩阵 问题1：

题目来源：AcWing

题目链接：756. 蛇形矩阵 - 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

之前无意之间看见一位大佬写的Python题解：

代码如下：

AC code 1:

#python代码
x=[0,1,0,-1]
y=[1,0,-1,0]
cnt=1
m,n=map(int,input().split()) // 输入 m,n
z=[[0 for i in range(n)] for j in range(m)]
i=0
j=0
k=0
z[i][j]=1
while cnt=m) or (j+y[k]<0) or (j+y[k]>=n) or (z[i+x[k]][j+y[k]]!=0) ):
        k=(k+1)%4
    i=i+x[k]
    j=j+y[k]
    cnt+=1
    z[i][j]=cnt
for i in range(m):
    for j in range(n):
        print(z[i][j],end=" ")
    print()

'''
作者：namelessstory
链接：https://www.acwing.com/file_system/file/content/whole/index/content/3564460/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
'''

由于我是主C++选手，于是凭借着我自学的一点点Python基础，把代码转换成了C++，代码如下：

AC code 2:

#include

using namespace std;

int z[110][110];
int main()
{
	int x[4]={0,1,0,-1};
	int y[4]={1,0,-1,0};
	int cnt=1;
	int m,n;
	cin>>m>>n;
	
	for(int i=0;i=m) || (j+y[k]<0) || (j+y[k]>=n) || (z[i+x[k]][j+y[k]]!=0) )
        	k=(k+1)%4;
   		i=i+x[k];
    	j=j+y[k];
   		cnt++;
  		z[i][j]=cnt;
	}
	for(int i=0;i 
emm...大佬写的代码就是不一样，看了半天没看懂解题思路。于是我就先试着调试并提交了一下，果然Accepted。
 
之前在洛谷也看到了一个类似的题目。
 
问题2： 
题目链接：P5731 【深基5.习6】蛇形方阵 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
 
题目描述
 
给出一个不大于 9 的正整数 n，输出 n×n 的蛇形方阵。
 
从左上角填上 1 开始，顺时针方向依次填入数字，如同样例所示。注意每个数字有都会占用 3 个字符，前面使用空格补齐。
 
输入格式
 
无
 
输出格式
 
无
 
输入输出样例
 
输入 #1
 
4
 
输出 #1
 
  1  2  3  4
 12 13 14  5
 11 16 15  6
 10  9  8  7
 
 
我们再来看这道题，与之前那道题不同的是，此题输出的是 n×n 的方阵，其实只需对代码稍加修改即可。即将代码中的m换成n，同时只需要输入一个变量n即可。
 
（注意：此题的输出格式要求每个数字占用 3 个字符，前面使用空格补齐！！！）
 
（否则一个测试点都通过不了，直接WA！！！）
 
代码如下：
 
AC code 3:
 
#include
using namespace std;

int z[110][110];
int main()
{
	int x[4]={0,1,0,-1};
	int y[4]={1,0,-1,0};
	int cnt=1;
	int n;
	cin>>n;
	
	for(int i=0;i=n) || (j+y[k]<0) || (j+y[k]>=n) || (z[i+x[k]][j+y[k]]!=0) )
        	k=(k+1)%4;
   		i=i+x[k];
    	j=j+y[k];
   		cnt++;
  		z[i][j]=cnt;
	}
	for(int i=0;i 
虽然该题成功的AC了，但那位AcWing大佬写题解我还是一脸懵，于是我又翻了翻洛谷题目下的题解，翻到了一个感觉还是比较容易理解的，先附上这位大佬的代码：
 
AC code 4:（注意该代码是从num[1][1]开始填充的）
 
#include
using namespace std;
int num[109][109],n;
int main()
{
	num[1][1]=1;//初始为1
	cin>>n;
	for(int i=1,j=1,tot=1;tot 0&&!num[i][j])num[i][j]=++tot;++j;//向左
		while(--i> 0&&!num[i][j])num[i][j]=++tot;++i;//向上
		//注意上面几行末尾的处理(--j这种)，不满足前面条件才会退出，这样进入下一个循环时实际上变量会有点问题。
		//举个例子：第一行写完，j=n+1，然后进入第二个while就根本不是在填表了（歪了）。
	}
	for(int i=1;i<=n;++i,cout< 
其实代码的主要核心思想就是：一开始先向右填，按照右、下、左、上顺时针方向依次填充，但同时要保证该位置还没有未被填过（即仍为0），直到 tot 等于 n*n 时退出循环。
 
看了大佬写的代码，理清思路，于是我按照这种思路尝试着写了一下代码：
 
AC code 5:（注意这个代码是从a[0][0]开始填充的）
 
#include
using namespace std;

int main()
{
	int n;
	cin>>n;
	int a[n][n];
	for(int i=0;i=0 && a[i][j]==0;)
		while(--j>=0 && a[i][j]==0)	// 向左 
			a[i][j]=(++c);
			j++;
//		for(;--i>=0 && a[i][j]==0;)
		while(--i>=0 && a[i][j]==0) // 向上 
			a[i][j]=(++c);
			i++;
	}
	for(int i=0;i 
我们来运行以下这个代码：
 
【运行结果】
 
 
这时，我们再来回到AcWing的蛇形矩阵那道题，对代码稍作修改即可。
 
代码如下：
 
AC code 6:
 
#include
using namespace std;

int main()
{
	int m,n;
	cin>>m>>n;
	int a[m][n];
	for(int i=0;i=0 && a[i][j]==0;)
		while(--j>=0 && a[i][j]==0)	// 向左 
			a[i][j]=(++c);
			j++;
//		for(;--i>=0 && a[i][j]==0;)
		while(--i>=0 && a[i][j]==0) // 向上 
			a[i][j]=(++c);
			i++;
	}
	for(int i=0;i 
来运行一下代码：
 
【运行结果】
 
 
 这样我们就解决了蛇形矩阵这类问题lalala~
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702480.html