一、问题的提出
n阶折线蛇形矩阵的特点是按照图1所示的方式排列元素。n阶蛇形矩阵是指矩阵的大小为n×n,其中n为正整数。
题目背景
一个 n 行 n 列的螺旋矩阵可由如图1所示的方法生成,观察图片,找出填数规律。填数规则为从 1 开始填到 n×n。
图1 8行8列的螺旋矩阵
现在给出矩阵大小 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复制
51
说明/提示
子任务
对于 30% 的测试数据,n≤10;对于 60% 的测试数据,n≤100;对于 100% 的测试数据,n≤1,000;特别地,对于 20% 的测试数据,i=j=1。
二、解题的思路
由图2可知,这是个水平、垂直转弯的蛇形矩阵。仔细看图2发现:当在第1行(行号为0)时则向右(行号不变,列号加1)填数,然后向下,当行列值相等转向左侧,如是列号到0时则向下(行号加1),然后向右方填数,如行列值相等则转向上,如是行号到0时则向右(行号不变,列号加1),然后向下,如此重复直到最后行的0列,或最后列的0行为止。
图2 蛇形矩阵分析图
三、矩阵生成算法
n行n列,第一行为0行,第一列为0列。从(0, 0)由1开始,方向设为向上。
当向上时,如行号已为0则列号加1、方向向反(向下),否则行号减1,如列号为n-1且行号为0时结束填写。
当向下时,如列号==行号则转弯(向左),否则行号加1。
当向左时,如列号已为0则行号加1、方向向反(向右),否则列号减1,如行号为n-1且列号为0时结束填写。
当向右时,如行号==列号则转弯(向上),否则列号加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 == 0 and j >= n-1 and k == 1) or (i >= n-1 and j == 0 and k == 3):break # 向上填写时,最后1列并到0行 或 向左填写时,最后1行并到0列if k == 0: # 向右填写j +=1if i == j: # 转向向上k = 1elif k == 1: # 向上填写if i == 0: # 到0时,转下一列调头j += 1k = 2else:i -=1elif k == 2: # 向下填写i +=1if i == j: # 转向向左k = 3elif k == 3: # 向左填写if j == 0: # 到0时,转下一行调头i += 1k = 0else:j -=1cnt += 1N = 6
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 == 0 and j >= n-1 and k == 1) or (i >= n-1 and j == 0 and k == 3):break # 向上并最后1列到第0行 或 向左并最后1行到第0列if k == 0: # 向右填写j +=1if i == j: # 转向向上k = 1elif k == 1: # 向上填写if i == 0: # 向上到0行,列号加1并转向下j += 1k = 2else:i -=1elif k == 2: # 向下填写i +=1if i == j: # 转向向左k = 3elif k == 3: # 向左填写if j == 0: # 向左到0列,行号加1并转向右i += 1k = 0else:j -=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])
执行结果: