Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
117
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. roadOfMatr = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
  7.  
  8. StartS = []
  9.  
  10. for i in range(SizeOfRow):
  11. string = input().split()
  12. for j in range(SizeOfCol):
  13. if (string[j] == "S"):
  14. StartS.append(i)
  15. StartS.append(j)
  16. else:
  17. ix[i][j] = string[j]
  18.  
  19. CoordOfY = int(StartS[0])
  20. CoordOfX = int(StartS[1])
  21.  
  22. for i in range(SizeOfRow):
  23. for j in range(SizeOfCol):
  24. ix[i][j] = int(ix[i][j])
  25.  
  26. MatrixBorn = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
  27.  
  28. def road_reduce(main):
  29.  
  30. def great_path(key_mat, roadOfMatr, i, j):
  31.  
  32. if (i < CoordOfY or j < CoordOfX):
  33. return 0
  34. if (roadOfMatr[i][j] != -1):
  35. return roadOfMatr[i][j]
  36.  
  37. roadOfMatr[i][j] = max(great_path(key_mat, roadOfMatr, i - 1, j), great_path(key_mat, roadOfMatr, i, j - 1)) + key_mat[i][j]
  38.  
  39. return roadOfMatr[i][j]
  40.  
  41. maximum_sum = great_path(ix, MatrixBorn, len(ix) - 1, len(ix[0]) - 1)
  42. x, y = len(roadOfMatr[0]) - 1, len(roadOfMatr) - 1
  43. way = []
  44. while (x != CoordOfX or y != CoordOfY):
  45. way.append([y, x])
  46. if x - 1 < CoordOfX:
  47. y -= 1
  48. elif y - 1 < CoordOfY:
  49. x -= 1
  50. elif roadOfMatr[y - 1][x] == max(roadOfMatr[y - 1][x], roadOfMatr[y][x - 1]):
  51. y -= 1
  52. else:
  53. x -= 1
  54. way.append([CoordOfX, CoordOfY])
  55. return (way, maximum_sum)
  56.  
  57.  
  58. result = road_reduce(MatrixBorn)
  59. result[0].reverse()
  60. new_string = []
  61. print("Path:")
  62. for i in result[0]:
  63. print('({},{})'.format(i[0], i[1]), end=" ")
  64.  
  65. print("\nCoins:", result[1], ' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement