makut

619

Oct 21st, 2014
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. import copy
  2.  
  3. n = int(input())
  4. table = [list(map(int, list(input()))) for i in range(n)]
  5. ways = [[None] * n for i in range(n)]
  6. ways[0][0] = table[0][0]
  7. for i in range(1, n):
  8. ways[0][i] = ways[0][i - 1] + table[0][i]
  9. ways[i][0] = ways[i - 1][0] + table[i][0]
  10. for i in range(1, n):
  11. for j in range(1, n):
  12. ways[i][j] = min(ways[i - 1][j], ways[i][j - 1]) + table[i][j]
  13. position = [n - 1, n - 1]
  14. route = []
  15. while position != [0, 0]:
  16. y = position[0]
  17. x = position[1]
  18. if y == n - 1 and x == n - 1:
  19. route.append(copy.copy(position))
  20. if ways[y - 1][x] <= ways[y][x - 1]:
  21. position[0] -= 1
  22. route.append(copy.copy(position))
  23. else:
  24. position[1] -= 1
  25. route.append(copy.copy(position))
  26. elif y == 0:
  27. position[1] -= 1
  28. route.append(copy.copy(position))
  29. elif x == 0:
  30. position[0] -= 1
  31. route.append(copy.copy(position))
  32. else:
  33. if ways[y - 1][x] <= ways[y][x - 1]:
  34. position[0] -= 1
  35. route.append(copy.copy(position))
  36. else:
  37. position[1] -= 1
  38. route.append(copy.copy(position))
  39. route.append([0, 0])
  40. way = [['-'] * n for i in range(n)]
  41. for coordinate in route:
  42. way[coordinate[0]][coordinate[1]] = '#'
  43. for i in range(n):
  44. print(''.join(list(map(str, way[i]))))
Advertisement
Add Comment
Please, Sign In to add comment