Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import copy
- n = int(input())
- table = [list(map(int, list(input()))) for i in range(n)]
- ways = [[None] * n for i in range(n)]
- ways[0][0] = table[0][0]
- for i in range(1, n):
- ways[0][i] = ways[0][i - 1] + table[0][i]
- ways[i][0] = ways[i - 1][0] + table[i][0]
- for i in range(1, n):
- for j in range(1, n):
- ways[i][j] = min(ways[i - 1][j], ways[i][j - 1]) + table[i][j]
- position = [n - 1, n - 1]
- route = []
- while position != [0, 0]:
- y = position[0]
- x = position[1]
- if y == n - 1 and x == n - 1:
- route.append(copy.copy(position))
- if ways[y - 1][x] <= ways[y][x - 1]:
- position[0] -= 1
- route.append(copy.copy(position))
- else:
- position[1] -= 1
- route.append(copy.copy(position))
- elif y == 0:
- position[1] -= 1
- route.append(copy.copy(position))
- elif x == 0:
- position[0] -= 1
- route.append(copy.copy(position))
- else:
- if ways[y - 1][x] <= ways[y][x - 1]:
- position[0] -= 1
- route.append(copy.copy(position))
- else:
- position[1] -= 1
- route.append(copy.copy(position))
- route.append([0, 0])
- way = [['-'] * n for i in range(n)]
- for coordinate in route:
- way[coordinate[0]][coordinate[1]] = '#'
- for i in range(n):
- print(''.join(list(map(str, way[i]))))
Advertisement
Add Comment
Please, Sign In to add comment