Advertisement
OMEGAHEAD_MonkoX

Untitled

Mar 5th, 2020
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. def Vivod(vec, n, m):
  2. for i in range(n):
  3. for j in range(m):
  4. print(vec[i][j], end = ' ')
  5. print()
  6.  
  7.  
  8. def fibbi(n, m, vec2):
  9.  
  10.  
  11. vec = [[0] * m for i in range(n)]
  12. vec3 = [[0] * m for i in range(n)]
  13. k = 0
  14.  
  15. if vec2[0][0] == 1:
  16. vec[0][0] = 1
  17. vec3[0][0] = 1
  18. k = 1
  19.  
  20. for i in range(1, m):
  21. if vec2[0][i] == 1:
  22. vec[0][i] = 1
  23. vec3[0][i] = k + 1
  24. k += 1
  25. else:
  26. break
  27.  
  28. if vec2[0][0] == 1:
  29. k = 1
  30. else:
  31. k = 0
  32.  
  33. for i in range(1, n):
  34. if vec2[i][0] == 1:
  35. vec[i][0] = 1
  36. vec3[i][0] = k + 1
  37. k += 1
  38. else:
  39. break
  40.  
  41. k = 0
  42.  
  43.  
  44. for i in range(1, n):
  45. for j in range(1, m):
  46. if vec2[i][j] == 1:
  47. if vec2[i - 1][j] == 0 and vec2[i][j - 1] == 0:
  48. vec[i][j] = 0
  49. vec3[i][j] = 0
  50. continue
  51.  
  52. if vec2[i - 1][j] == 0:
  53. vec[i][j] = vec[i][j - 1]
  54. vec3[i][j] = vec3[i][j - 1] + 1
  55. continue
  56.  
  57. if vec2[i][j - 1] == 0:
  58. vec[i][j] = vec[i - 1][j]
  59. vec3[i][j] = vec3[i - 1][j] + 1
  60. continue
  61.  
  62. vec[i][j] = vec[i - 1][j] + vec[i][j - 1]
  63. vec3[i][j] = min(vec3[i - 1][j], vec3[i][j - 1]) + 1
  64.  
  65.  
  66. # Vivod(vec, n, m)
  67.  
  68. if vec2[n - 1][m - 1] == 0 or vec[n - 1][m - 1] == 0 or vec3[n - 1][m - 1] == 0 or vec2[0][0] == 0 or vec3[n - 1][m - 1] > n + m - 1:
  69. print("Impossible")
  70. exit(0)
  71.  
  72.  
  73. print(vec[n - 1][m - 1])
  74.  
  75.  
  76.  
  77. n, m = map(int, input().split())
  78. vec2 =[[int(j) for j in input().split()] for i in range(n)]
  79. fibbi(n, m, vec2)
  80.  
  81. """
  82. входные данные
  83. 3 5
  84. 1 1 1 1 1
  85. 1 0 1 0 1
  86. 1 1 1 1 1
  87. """
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement