蓝桥杯基础练习VIP-回形取数-题解（Python代码）

解题思路:

方法一：时间复杂度O(n2)用python实现超时32%。用C/C++或Java同样的思路是可以AC的。

方法二：时间复杂度O(n),这个方法来源于 传送门 思路是在O(n2)基础上将里面的一层循环去掉、不过要加一个标记标明接下来要走的方向，下"D",右"R",上"U",左"L"，以最外层的循环遍历判断然后对要走的方向进行更新。这样就可以将时间复杂降为O(n)
参考代码:

方法一：

n,m = map(int,input().split())
mapL = [list(map(int,input().split())) for _ in range(m)]
count,x,y = 1,0,0
print(mapL[0][0],end=" ")
mapL[0][0] = 0

while count < n*m:
    """向下走,y+1"""
    while y+1<m and mapL[y+1][x] != 0:
        y += 1
        if count == n*m -1:
            print(mapL[y][x],end="")
        else:
            print(mapL[y][x],end=" ")
        mapL[y][x] = 0
        count += 1
    """走到底后左转向右走，x+1"""
    while x+1=0 and mapL[y-1][x] != 0:
        y -= 1
        if count == n*m -1:
            print(mapL[y][x],end="")
        else:
            print(mapL[y][x],end=" ")
        mapL[y][x] = 0
        count += 1
    """走到最上面后左转、向左走x-1"""
    while x-1 >=0 and mapL[y][x-1] != 0:
        x -= 1
        if count == n*m -1:
            print(mapL[y][x],end="")
        else:
            print(mapL[y][x],end=" ")
        mapL[y][x] = 0
        count += 1

方法二：

m,n = map(int,input().split())
mapL = [list(map(int,input().split())) for _ in range(m)]
i,j = 0,0    #i表示行，j表示列
flag = "D"    #从向下走开始
result = []    #存结果
while True:
    if i<0 or j<0 or i>=m or j>=n or mapL[i][j] == -1:    #“i<0 or j<0 or i>=m or j>=n”这一段要加，不然一些单行，单列（n=1 or m=1）的用例通不过
        break
    result.append(mapL[i][j])
    mapL[i][j] = -1
    if flag == "D":
        i += 1
    elif flag == "R":
        j += 1
    elif flag == "U":
        i -= 1
    elif flag == "L":
        j -= 1
    if flag == "D" and (i>=m or mapL[i][j]==-1):
        flag = "R"
        i -= 1
        j += 1
    elif flag == "R" and (j>=n or mapL[i][j]==-1):
        flag = "U"
        j -= 1
        i -= 1
    elif flag == "U" and (i<0 or mapL[i][j] == -1):
        flag = "L"
        i += 1
        j -= 1
    elif flag == "L" and (j<0 or mapL[i][j] == -1):
        flag = "D"
        j += 1
        i += 1
        
for i in range(len(result)):
    if i == len(result) -1:
        print(result[i])
    else:
        print(result[i],end=" ")