• API
• FAQ
• Tools
• Archive
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.
29.
30.     def great_path(key_mat, roadOfMatr, i, j):
31.
32.         if (i < CoordOfY or j < CoordOfX):
33.             return 0
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.
40.
41.     maximum_sum = great_path(ix, MatrixBorn, len(ix) - 1, len(ix[0]) - 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
51.             y -= 1
52.         else:
53.             x -= 1
54.     way.append([CoordOfX, CoordOfY])
55.     return (way, maximum_sum)
56.
57.