旋转生成矩阵(Spiral Matrix)

Posted on In

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,

Given n = 3,

You should return the following matrix:

[[ 1, 2, 3 ],

[ 8, 9, 4 ],

[ 7, 6, 5 ]]

与之前蛇形遍历一个思路，给定几个状态x,y,state(说明当前生成的方向)

在这个问题中，只有以下几种情况：向上生成到顶时，向右生成；向右生成到顶时，向下生成；向下生成到顶时，向左生成；向左生成到顶时，向上生成。最终的结束条件是生成了n^2个数字。

首先生成一个n*n的矩阵：

1
2
3
4
5
rs = []
for i in range(n):
    rs.append([])
    for j in range(n):
        rs[i].append(None)

这样就得到了一个n*n的空矩阵。

开始时尝试过

1
[[None]*n]*n

与

1
[[None for i in range(n)]]*n

的方式，发现均会出现问题。原因是以这种方式生成的二维数组的子项指向的是同一个对象。其后果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = [[None]*5]*5
>>> a
[[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None], 
[None, None, None, None, None]]
>>> a[2][2] = 1
>>> a
[[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None], 
[None, None, 1, None, None]]

使用built-in查看它们的id发现：

1
2
>>> id(a[2]),id(a[3])
(4337281432, 4337281432)

因此放弃看上去简洁的写法。

更新：发现一个简洁有效的写法：

1
x = [[None for i in range(n)] for j in range(n)]

之后找出每个方向的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
while step <= n**2:
# print x,y,state,step,layer,tmp
    rs[x][y] = step
    if state == 'up':
        if x == layer:
            y += 1
            state = 'right'
        else:x -= 1
    elif state == 'right':
        if y+1 == n-layer:
            x += 1
            state = 'down'
        else:y+=1
    elif state == 'down':
        if x+1 == n-layer:
            y -= 1
            state = 'left'
        else:x+=1
    elif state == 'left':
        if y == layer:
            x-=1
            state= 'up'
        else:y-=1
    step += 1

大意如此。其中layer为当前从外向内已生成完的层数，由

1
if step == n**2-(n-layer*2-2)**2:layer+=1

可以得到。