题目描述
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
题意:给定一个正整数 n,生成一个包含 1 到 $n^2$ 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
算法1
题解:我们用state
分别代表当前前进方向,[0,1,2,3]
分别代表上下左右,初始时state = 1
,(x,y)
代表上一个填充的位置,(next_x,next_y)
代表即将要填充的位置,其中(x,y)
初始化为(0,-1)
,是为了让第一次要填充的位置是(0,0)
,val
代表当前要填充的数字。如果位置(next_x,next_y)
越界或者已经填充过了,那么我们将方向顺时针旋转90度,state = (state + 1) % 4
。如果没有填充过,那么填充val
同时更新val,x,y
。
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n,vector<int>(n,0));
int state = 1,x = 0,y = -1;
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
for(int val = 1 ; val <= n * n ;)
{
int next_x = x + dx[state],next_y = y + dy[state];
if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < n && res[next_x][next_y] == 0)
{
res[next_x][next_y] = val ++;
x = next_x,y = next_y;
}
else
state = (state + 1) % 4;
}
return res;
}