Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- start = input().split()
- SizeOfRow = int(start[0])
- SizeOfCol = int(start[1])
- ix = [[0 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
- roadOfMatr = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
- StartS = []
- for i in range(SizeOfRow):
- string = input().split()
- for j in range(SizeOfCol):
- if (string[j] == "S"):
- StartS.append(i)
- StartS.append(j)
- else:
- ix[i][j] = string[j]
- CoordOfY = int(StartS[0])
- CoordOfX = int(StartS[1])
- for i in range(SizeOfRow):
- for j in range(SizeOfCol):
- ix[i][j] = int(ix[i][j])
- MatrixBorn = [[-1 for j in range(SizeOfCol)] for i in range(SizeOfRow)]
- def road_reduce(main):
- def great_path(key_mat, roadOfMatr, i, j):
- if (i < CoordOfY or j < CoordOfX):
- return 0
- if (roadOfMatr[i][j] != -1):
- return roadOfMatr[i][j]
- roadOfMatr[i][j] = max(great_path(key_mat, roadOfMatr, i - 1, j), great_path(key_mat, roadOfMatr, i, j - 1)) + key_mat[i][j]
- return roadOfMatr[i][j]
- maximum_sum = great_path(ix, MatrixBorn, len(ix) - 1, len(ix[0]) - 1)
- x, y = len(roadOfMatr[0]) - 1, len(roadOfMatr) - 1
- way = []
- while (x != CoordOfX or y != CoordOfY):
- way.append([y, x])
- if x - 1 < CoordOfX:
- y -= 1
- elif y - 1 < CoordOfY:
- x -= 1
- elif roadOfMatr[y - 1][x] == max(roadOfMatr[y - 1][x], roadOfMatr[y][x - 1]):
- y -= 1
- else:
- x -= 1
- way.append([CoordOfX, CoordOfY])
- return (way, maximum_sum)
- result = road_reduce(MatrixBorn)
- result[0].reverse()
- new_string = []
- print("Path:")
- for i in result[0]:
- print('({},{})'.format(i[0], i[1]), end=" ")
- print("\nCoins:", result[1], ' ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement