Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.72 KB | None | 0 0
  1. start = input().split()
  2. SizeOfRow = int(start[0])
  3. SizeOfCol = int(start[1])
  4.  
  5. ix = [[0 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
  6. ix = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
  7. StartS = []
  8.  
  9. for i in range(SizeOfRow):
  10. string = input().split()
  11. for j in range(SizeOfCol):
  12. if (string[j] == "S"):
  13. StartS.append(i)
  14. StartS.append(j)
  15. else:
  16. ix[i][j] = string[j]
  17.  
  18. CoordOfY = int(StartS[0])
  19. CoordOfX = int(StartS[1])
  20.  
  21. for i in range(SizeOfRow):
  22. for j in range(SizeOfCol):
  23. ix[i][j] = int(ix[i][j])
  24.  
  25. MatrixBorn = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
  26.  
  27. def road_reduce(roadOfMatr):
  28.  
  29. def great_path(key_mat, roadOfMatr, i, j):
  30. if (i < CoordOfY or j < CoordOfX):
  31. return 0
  32. if (roadOfMatr[i][j] != -1):
  33. return roadOfMatr[i][j]
  34.  
  35. roadOfMatr[i][j] = max(great_path(key_mat, roadOfMatr, i - 1, j), great_path(key_mat, roadOfMatr, i, j - 1)) + key_mat[i][j]
  36. return roadOfMatr[i][j]
  37.  
  38. maximum_sum = great_path(ix, MatrixBorn, len(ix) - 1, len(ix[0]) - 1)
  39. x, y = len(roadOfMatr[0]) - 1, len(roadOfMatr) - 1
  40. way = []
  41. while (x != CoordOfX or y != CoordOfY):
  42. way.append([y, x])
  43. if x - 1 < CoordOfX:
  44. y -= 1
  45. elif y - 1 < CoordOfY:
  46. x -= 1
  47. elif roadOfMatr[y - 1][x] == max(roadOfMatr[y - 1][x], roadOfMatr[y][x - 1]):
  48. y -= 1
  49. else:
  50. x -= 1
  51. way.append([CoordOfY, CoordOfX])
  52. return (way, maximum_sum)
  53.  
  54.  
  55. road_back = road_reduce(MatrixBorn)
  56. road_back[0].reverse()
  57. new_string = []
  58. print("Path:")
  59. for i in road_back[0]:
  60. print('({},{})'.format(i[0], i[1]), end=" ")
  61.  
  62. print("\nCoins:", road_back[1], ' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement