SHARE
TWEET

Untitled

a guest Dec 15th, 2019 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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], ' ')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top