信息学竞赛经典题目蛇形填数向量旋转解法

下面是我研究的向量旋转法,又和”海龟”扯上联系了。一只看不见的“小海龟”在数组中通过二维向量旋转90度，让它只能上下左右移动。在程序中设计了一个叫ArrayTurtle的类。它有step方法让对象在array中前进或者倒退一个单位。最关键的是turn方法，让对象旋转90度。数学理论来源于二维向量旋转。如下图所示：

以下是源代码：

"""Python信息学竞赛蛇形填数向量旋转法.py by 李兴球"""
class ArrayTurtle:
    def __init__(self,i,j,h,array):
        """i:初始行位置,j:初始列位置,
           h:二元组,表示初始方向,array:二维数组"""
        self.i = i
        self.j = j
        self.h = h                # 下(1,0),左(0,-1),上(-1,0),右(0,1)
        self.array = array
        self.rows = len(array)    # 总行数
        self.cols = len(array[0]) # 总列数
        self.mileage = 1          # 用于统计里程(假定在初始位置就有1个里程了)
        self.set_value()
        self.matrix = [(0,-1),(1,0)] # 变换矩形
        
    def step(self,k=1):          # 前进1格或者-1格        
        self.i += int(self.h[0]) * k
        self.j += int(self.h[1]) * k
        self.mileage += k
        
    def set_value(self):
        
        #self.array[self.i][self.j] = self.mileage
        self.array[self.i][self.j] = self.rows*self.cols + 1 - self.mileage
        
    def current_value(self):
        return self.array[self.i][self.j]
    
    def goto_end(self):
        return self.mileage == self.rows*self.cols
    
    def beyond_boundary(self):
        """超出边界"""
        return self.i<0 or self.i>=self.rows or \
               self.j<0 or self.j>=self.cols
        
    def turn(self):                # 左转向90度
        # 矩形乘法
        x = self.h[0] * self.matrix[0][0] + self.h[1] * self.matrix[0][1]
        y = self.h[0] * self.matrix[1][0] + self.h[1] * self.matrix[1][1]
        self.h = (x,y)    

    def display(self):
        for row in self.array:
            for col in row:
                print(f"{col:3d}",end=' ')
            print()
        print()

n = 8
matrix = [ [0 for i in range(n)] for i in range(n)]

i,j = 0,0
t = ArrayTurtle(i,j,(1,0),matrix)
t.set_value()
while True:
    while True:
        t.step(1)              # 在当前方向前进一个单位
        if  not t.beyond_boundary() and t.current_value()==0:   # 没超出边界或没走过,则倒退
           t.set_value()
        else:
           t.step(-1)
           break        
    t.turn()
    if t.goto_end():break

t.display()   
    

Python信息学竞赛蛇形填数向量旋转法.py by李兴球