C++ 蛇形矩阵
蛇形矩阵 (C++)
输入两个整数
n
n
n和
m
m
m,输出一个
n
n
n行
m
m
m列的矩阵,将数字
1
1
1到
n
×
m
n×m
n×m按照回字蛇形填充至矩阵中。
具体矩阵形式可参考样例。
输入格式
输入共一行,包含两个整数 n n n和 m m m。
输出格式
输出满足要求的矩阵。
矩阵占
n
n
n行,每行包含
m
m
m个空格隔开的整数。
数据范围
1 ≤ n , m ≤ 100 1≤n,m≤100 1≤n,m≤100
输入样例:
3 3
输出样例:
1 2 3
8 9 4
7 6 5
代码:
#include <iostream>
using namespace std;
const int N = 110;
int main()
{
int n, m, a, b;
cin >> n >> m;
int Q[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int x = 0, y = 0, d = 1;
for(int i = 1 ;i <= n*m; i++) {
Q[x][y] = i;
a = x + dx[d];
b = y + dy[d];
if(a < 0||a >= n||b < 0||b >= m||Q[a][b]) {
d = (d+1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m ; j++) {
cout << Q[i][j] << " ";
}
cout << endl;
}
return 0;
}
思路说明:
对于这种网格形状的二维数组,可以利用两个坐标变量dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}
来表示坐标的变化
如:对于数组中任意一处坐标
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0),它上右下左(顺时针转一圈)的点坐标分别为
(
x
0
−
1
,
y
0
)
,
(
x
0
,
y
0
+
1
)
,
(
x
0
+
1
,
y
0
)
,
(
x
0
,
y
0
−
1
)
(x_0-1,y_0),(x_0,y_0+1),(x_0+1,y_0),(x_0,y_0-1)
(x0−1,y0),(x0,y0+1),(x0+1,y0),(x0,y0−1),行坐标的变化量分别是
d
x
=
−
1
,
0
,
1
,
0
dx=-1,0,1,0
dx=−1,0,1,0,列坐标的变化量分别是
d
y
=
0
,
1
,
0
,
−
1
dy=0,1,0,-1
dy=0,1,0,−1,于是利用一个for
循环就可以遍历一个点
(
x
0
,
y
0
)
(x_0,y_0)
(x0,y0)周围的所有点,方法如下:
for(int i=0; i<4; i++) {
x1 = x0 + dx[i];
y1 = y0 + dy[i]
}
//第一次循环(x1,y1)=(x0-1,y0)为上方的点
//第二次循环(x1,y1)=(x0,y0+1)为右侧的点
//第三次循环(x1,y1)=(x0+1,y0)为下方的点
//第四次循环(x1,y1)=(x0,y0-1)为左侧的点
//每次循环得到的新坐标用x1,y1存储,而不对x0,y0直接进行修改,防止影响到下次循环的坐标
如果是需要遍历周围一圈8个位置,那就dx[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1}
,从左上角开始顺时针旋转。
在本题“蛇形矩阵”中,需要按照“蛇形”的顺序来对数组进行填充,即从 ( 0 , 0 ) (0,0) (0,0)坐标开始,按照右下左上(顺时针)的顺序移动坐标并填入数字,当移动到数组边界或已经填过数的位置时,需要按顺时针的顺序调整坐标移动的方向,具体实现如下:
for(int i = 1 ;i <= n*m; i++) {//循环次数为需要填入的数字个数
Q[x][y] = i;//按顺序从1到n*m填入数字
a = x + dx[d];//填完数字后更新坐标,这里用一个变量d来表示坐标更新的方向,d=0表示坐标向上移动一位,d=1右一位,d=2下一位,d=3左一位
b = y + dy[d];//用一个新的变量暂时保存新坐标(a,b),后续再对新的坐标进行是否出界的判断
if(a < 0||a >= n||b < 0||b >= m||Q[a][b]) {//判断新坐标是否出界,同时判断新的坐标是否已经有数了
d = (d+1) % 4;//由于蛇形矩阵移动的顺序是右下左上的顺时针顺序,所以直接让d加1就可以实现顺时针转弯的效果,注意这里要取模运算
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}