模拟填空法生成螺旋矩阵

螺旋矩阵是一个比较有意思的题目,不少online judge都喜欢出类似的题目,例如BUAA(国内不多的几个支持python的acm平台)的185题.以前曾经贴过一个matlab的快速螺旋矩阵函数,具体在这里.下面的方法是使用的模拟填空法.更容易理解一点.
代码如下:

#! /usr/bin/env python

# 生成螺旋矩阵,输入m是二维list,生成方法 m = [[0]*n for i in range(n)]
# 不能用 m = [[0]*n]*n,否则m[i]不独立,修改某个元素会造成所有对应位置都被修改
def getMat(mat,n):
    direction = 1   # 增长方向:1->,2\|/,3<-,4/|\
    i,j,ind = 0,0,1 # 初值,从(0,0)开始
    while ind<=n*n:
        if mat[i][j]==0:
            mat[i][j] = ind # 修改当前位置
            ind += 1        # 计数器加1
            if direction==1: # 如果向右
                if j+1<n and mat[i][j+1]==0: # 下一位置有效且下一位置是0
                    j += 1
                else: # 否则改变方向,下同
                    i += 1
                    direction = 2
            elif direction==2:
                if i+1<n and mat[i+1][j]==0:
                    i += 1
                else:
                    j -= 1
                    direction = 3
            elif direction==3:
                if j-1>=0 and mat[i][j-1]==0:
                    j -= 1
                else:
                    i -= 1
                    direction = 4
            elif direction==4:
                if i-1>=0 and mat[i-1][j]==0:
                    i -= 1
                else:
                    j += 1
                    direction = 1
    for i in range(n): # 打印结果
        for j in range(n):
            print mat[i][j],
        print