解题思路:
方法一:时间复杂度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=" ")
0.0分
18 人评分
数组输出 (C语言代码)错误???浏览:558 |
WU-蓝桥杯算法提高VIP-交换Easy (C++代码)浏览:1107 |
DNA (C语言代码)浏览:540 |
母牛的故事 (C语言代码)浏览:549 |
1013题解浏览:552 |
1012题解浏览:861 |
2^k进制数 (C语言描述,蓝桥杯)浏览:1420 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:486 |
C二级辅导-等差数列 (C语言代码)浏览:694 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:505 |