ulvis.paste.net

Paste Search Dynamic
Recent pastes
append
  1. m, n = map(int, input().split())
  2. cost = [[] for i in range(m)]
  3. for i in range(m-1, -1, -1):
  4.         cost[i] = [int(s) for s in input().split()]
  5. matrix = [[-1]*(n+1) for i in range(m+1)]
  6. matrix[1][1] = cost[0][0]
  7. path = []
  8. for i in range(1, m+1):
  9.         for j in range(1, n+1):
  10.                 if i==1 and j==1:
  11.                         continue
  12.                 matrix[i][j] = cost[i-1][j-1] + max(matrix[i-1][j], matrix[i][j-1])
  13.  
  14. i = m
  15. j = n
  16. while i+j>2:
  17.         if matrix[i-1][j] > matrix[i][j-1]:
  18.                 path.append('F')
  19.                 i -= 1
  20.         else:
  21.                 path.append('R')
  22.                 j -= 1
  23. path = path[::-1]              
  24. print(*path, sep="")
Parsed in 0.006 seconds