AcWing-756.蛇形矩阵 AcWing-756.蛇形矩阵

65 阅读 0 评论 43 点赞

我是靠谱客的博主苹果母鸡，最近开发中收集的这篇文章主要介绍AcWing-756.蛇形矩阵 AcWing-756.蛇形矩阵，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

AcWing-756.蛇形矩阵

一、问题描述

输入两个整数 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

二、分析与代码

分析
输出时是将数字1到n×m依次按照回字蛇形填充至矩阵中，则可数字将1到n×m依次放入矩阵中对应的位置，再将整个矩阵输出。

难点
如何将每一个数字放入矩阵中的对应位置？
答：数字在矩阵中的摆放规律是，从数字1开始依次向右方递增，当递增到右边界时，则开始向下方递增，当递增到下边界时，则开始向左方递增，当递增到左边界时，依次向上方递增，当递增到上边界时，再重新开始向右方递增，直到将n×m个数都放入矩阵中。
注意：在向某个方向递增时，当递增至矩阵边界或已经赋值的位置时，则按以上规律更改递增方向，即矩阵中同一位置不可进行两次赋值。

方法
可通过设置两个数组：
dx[4]={0,1,0,-1}
dy[4]={1,0,-1,0}
来控制递增方向，dx代表竖直方向，dy代表水平方向，具体方法如下：
设置一整型变量d作为下标，用来选择dx与dy数组中的数据。
d=0时，dx[d]=0，dy[d]=1，代表竖直方向为0，水平方向为1，即递增方向为水平向右递增，竖直方向不变。
d=1时，dx[d]=1，dy[d]=0，代表竖直方向为1，水平方向为0，即递增方向为竖直向下递增，水平方向不变。
d=2时，dx[d]=0，dy[d]=-1，代表竖直方向为0，水平方向为-1，即递增方向为水平向左递增，竖直方向不变。
d=3时，dx[d]=-1，dy[d]=0，代表竖直方向为-1，水平方向为0，即递增方向为竖直向上递增，水平方向不变。

具体代码

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int snake[n][m];
int i,j,num,d=0,a,b;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
snake[i][j]=0;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
i=0;
j=0;
for(num=1;num<=n*m;num++)
{
snake[i][j]=num;
a=i+dx[d];
//dx的值代表水平递增方向，i+dx即可得到下一位置的横下标
b=j+dy[d];
//dy的值代表竖直递增方向，j+dy即可得到下一位置的纵下标
//最好将snake数组先初始化为全0，若不初始化直接使用if(snake[][])判断数组是否赋值的话不准确，有时操作系统划分给snake的空间有脏数据
if(a<0||a>=n||b<0||b>=m||snake[a][b]!=0)
//判断是否到边界
{
d=(d+1)%4;
a=i+dx[d],b=j+dy[d];
}
i=a;
j=b;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
printf("%d ",snake[i][j]);
printf("n");
}
return 0;
}