一、問題的提出

n階蛇形矩陣的特點是按照圖1所示的方式排列元素。n階蛇形矩陣是指矩陣的大小為n×n，其中n為正整數。

題目背景

一個?n?行?n?列的螺旋矩陣可由如圖1所示的方法生成，觀察圖片，找出填數規律。填數規則為從?1?開始填到?n×n。

圖1??n?行?n?列的螺旋矩陣(蛇形矩陣)

?現在給出矩陣大小?n?以及?i?和?j，請你求出該矩陣中第?i?行第?j?列的數是多少。

題目描述

無

輸入格式

從標準輸入讀入數據。 共一行，包含三個整數?n（1≤n≤1,000）、i（1≤i≤n）、j（1≤j≤n），每兩個整數之間用一個空格隔開，分別表示矩陣大小、待求的數所在的行號和列號。

輸出格式

輸出到標準輸出。 一個整數，表示相應矩陣中第?i?行第?j?列的數。

輸入輸出樣例

輸入 #1復制

8 2 8

輸出 #1復制

43

說明/提示

子任務

• 對于?30%?的測試數據，n≤10；
• 對于?60%?的測試數據，n≤100；
• 對于?100%?的測試數據，n≤1,000；
• 特別地，對于?20%?的測試數據，i=j=1。

提示

根據本題的填數規則，一個?8×8?的螺旋矩陣應該長這樣(如圖2所示)：

圖2 8行8列的螺旋矩陣(蛇形矩陣)

?二、解題的思路

由圖3可知，這是個旋轉45o的Z形矩陣，當然折返長度是不相等的。仔細看圖1發現：當向右上方填數時，如行號為0則向右(行號不變，列號加1)，如是列號到n時則向下(列號減1，行號加1)，然后向左下方填數，此時，如列號為0則向下，如是行號到n時則向右(行號減1，列號加1)，然后向右一方填數，如此重復直到最后行、最后列填完為止。

圖3 蛇形矩陣分析圖

三、矩陣生成算法

n行n列，第一行為0行，第一列為0列。從(0,0)由1開始，方向設為從左下往右上。

當從左下往右上時，如行號已為0則列號加1方向向反(從右上往左下)，否則行號減1，列號加1，如列號達n則列號為n-1，行號加1方向向反(從右上往左下)。

當從右上往左下時，如列號已為0則行號加1方向向反(從左下往右上)，否則行號加1，列號減1，如行號達n則列號加1，行號為n-1方向向反(從左下往右上)。

當行號和列號都為n-1時結束。

程序代碼如下：

def prt(hm):???????????????? # 打印二維列表for i in range(N):for j in range(N):print("%3d" % hm[i][j], end='')print()def Helix_MatrixII(n):cnt = 1i = j = 0k = 1while True:matrix[i][j] = cntif i == n-1 and j == n-1:breakif k == 1:?????????? # 從左下往右上 if i == 0 :j += 1if j >= n:j = n-1i = i+1 if i < n -1 else n-1k = -1elif j == n-1:i += 1k = -1else:i -= 1j += 1else:?????????       # 從右上往左下if j == 0 :i += 1if i >= n:i = n-1j = j+1 if j < n -1 else n-1k = 1elif i == n-1:j += 1k = 1else:i += 1j -= 1cnt += 1N = 7
matrix = []???????????? # 初始化二維矩陣matrix(二維列表)
for i in range(N):matrix.append([])for j in range(N):matrix[i].append(0)
Helix_MatrixII(N)
prt(matrix)

執行結果：

?四、題目求解算法

題目要求輸入矩陣規模n和坐標(i, j)三個參數，求出矩陣(i, j)處的元素值。所以先按n求出矩陣，現按坐標輸出元素值。

程序代碼如下：

def Helix_MatrixII(n):cnt = 1i = j = 0k = 1while True:matrix[i][j] = cntif i == n-1 and j == n-1:breakif k == 1:        # 從左下往右上if i == 0 :j += 1if j >= n:j = n-1i = i+1 if i < n -1 else n-1k = -1elif j == n-1:i += 1k = -1else:i -= 1j += 1else:             # 從右上往左下if j == 0 :i += 1if i >= n:i = n-1j = j+1 if j < n -1 else n-1k = 1elif i == n-1:j += 1k = 1else:i += 1j -= 1cnt += 1N, x, y = map(int, input().split())
matrix = []????????????   # 初始化二維矩陣matrix(二維列表)
for i in range(N):matrix.append([])for j in range(N):matrix[i].append(0)
Helix_MatrixII(N)
print(matrix[x-1][y-1])

執行結果：

?