Advertisement
Guest User

Untitled

a guest
Feb 20th, 2018
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.76 KB | None | 0 0
  1.  
  2. def main():
  3. n, m = map(int,raw_input().split())
  4. from math import sqrt
  5. a = [[0] * (n + 1) for i in range(m + 1)]
  6. b = [[0] * (n + 1) for i in range(m + 1)]
  7. e = sqrt(2) * 100
  8. k = int(raw_input())
  9. for i in range(k):
  10. x, y = map(int,raw_input().split())
  11. b[y][x] = 1
  12. a[0][0] = 0
  13. for i in range (1, n + 1):
  14. a[0][i] = a[0][i - 1] + 100
  15. for j in range(1, m + 1):
  16. a[j][0] = a[j - 1][0] + 100
  17. for i in range(1, m + 1):
  18. for j in range(1, n + 1):
  19. if b[i][j] == 1:
  20. a[i][j] = min(a[i - 1][j - 1] + e, a[i - 1][j] + 100, a[i][j - 1] + 100)
  21. else:
  22. a[i][j] = min(a[i - 1][j] + 100, a[i][j - 1] + 100)
  23. print(int(a[m][n]))
  24. main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement