Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.55 KB | None | 0 0
  1. # import sys
  2. # from math import *
  3. # from copy import copy
  4. from pprint import pprint
  5. import pdb
  6. import sys
  7. sys.setrecursionlimit(1000000)
  8. # import itertools
  9. # from pprint import pprint
  10. from collections import deque
  11. # import sys
  12. f = open('input.txt', 'r')
  13. # o = open('input.txt', 'w')
  14.  
  15. input = sys.stdin.readline
  16.  
  17.  
  18. def print(*args, sep=' ', end='\n'):
  19. s = ''
  20. for i in args:
  21. s += str(i) + sep
  22. s += end
  23. sys.stdout.write(s)
  24.  
  25.  
  26.  
  27.  
  28. def rI():
  29. return [int(i) for i in f.readline().split()]
  30.  
  31.  
  32. # print(rI())
  33. n, m, k = rI()
  34. idat = [None for i in range(n)]
  35. for ix in range(len(idat)):
  36. idat[ix] = list(f.readline().strip()) + ['.']
  37. idat.append(['.' for i in range(m + 1)])
  38.  
  39. gr = {}
  40. iscycle = {}
  41. cycletype = {}
  42. vis = {}
  43. for i in [0, 1]:
  44. for a in range(n + 1):
  45. for b in range(m + 1):
  46. gr[i, a, b] = []
  47. vis[i, a, b] = False
  48. iscycle[i, a, b] = False
  49.  
  50. for a in range(n):
  51. for b in range(m):
  52. if(idat[a][b] == '.'):
  53. continue
  54. if(idat[a][b] == '/'):
  55. gr[1, a, b].append([0, a, b])
  56. gr[0, a, b].append([1, a, b])
  57. gr[0, a + 1, b].append([1, a, b + 1])
  58. gr[1, a, b + 1].append([0, a + 1, b])
  59. else:
  60. gr[0, a, b].append([1, a, b + 1])
  61. gr[1, a, b + 1].append([0, a, b])
  62. gr[1, a, b].append([0, a + 1, b])
  63. gr[0, a + 1, b].append([1, a, b])
  64.  
  65. # pprint(gr)
  66. # pdb.set_trace()
  67. out = 0
  68. kolcik = 0
  69.  
  70.  
  71. def dfs(a, st, fr):
  72. vis[a] = True
  73. for i in gr[a]:
  74. i = tuple(i)
  75. if(i == st) and (st != fr):
  76. global kolcik
  77. kolcik += 1
  78. que = deque()
  79. que.append(i)
  80. # pdb.set_trace()
  81. while(len(que) != 0):
  82. curr = que.popleft()
  83. iscycle[curr] = True
  84. cycletype[curr] = kolcik
  85. for ii in gr[curr]:
  86. ii = tuple(ii)
  87. if(iscycle[ii] == False):
  88. que.append(ii)
  89. # print(iscycle[ii])
  90. return
  91. if(vis[i] == False):
  92. dfs(i, st, a)
  93.  
  94.  
  95. for i in [0, 1]:
  96. for a in range(n + 1):
  97. for b in range(m + 1):
  98. # if(idat[a][b] == '.'):
  99. # continue
  100. if(vis[i, a, b] == False):
  101. if(len(gr[i, a, b]) == 0):
  102. continue
  103. # print(i, a, b)
  104. dfs((i, a, b), (i, a, b), ())
  105. out += 1
  106.  
  107.  
  108. for i in range(n):
  109. if(len(gr[1, i, m]) == 0):
  110. continue
  111. if(vis[1, i, m] == False):
  112. dfs((1, i, m), (1, i, m), ())
  113. out += 1
  114.  
  115. for i in range(m):
  116. if(len(gr[0, n, i]) == 0):
  117. continue
  118. if(vis[0, n, i] == False):
  119. dfs((0, n, i), (0, n, i), ())
  120. out += 1
  121.  
  122.  
  123. pv = 0
  124.  
  125.  
  126. def dfs_update(a, st, fr, typ):
  127. cycletype[a] = typ
  128. if(a == st):
  129. return
  130.  
  131. fist = tuple(gr[a][0])
  132. sec = tuple(gr[a][1])
  133. if(fr != fist):
  134. dfs_update(fist, st, a, typ)
  135. else:
  136. dfs_update(sec, st, a, typ)
  137.  
  138.  
  139. for a in range(n):
  140. for b in range(m):
  141. if(idat[a][b] == '.'):
  142. continue
  143. if(k == 0):
  144. break
  145. if(iscycle[0, a, b] == True and iscycle[0, a, b + 1] == True):
  146. if(cycletype[0, a, b] == cycletype[0, a, b + 1]):
  147. continue
  148. kolcik -= 1
  149. out -= 1
  150. k -= 1
  151. if(idat[a][b] == '/'):
  152. gr[1, a, b].remove([0, a, b])
  153. gr[0, a, b].remove([1, a, b])
  154. gr[0, a + 1, b].remove([1, a, b + 1])
  155. gr[1, a, b + 1].remove([0, a + 1, b])
  156.  
  157. gr[0, a, b].append([1, a, b + 1])
  158. gr[1, a, b + 1].append([0, a, b])
  159. gr[1, a, b].append([0, a + 1, b])
  160. gr[0, a + 1, b].append([1, a, b])
  161. else:
  162. gr[0, a, b].remove([1, a, b + 1])
  163. gr[1, a, b + 1].remove([0, a, b])
  164. gr[1, a, b].remove([0, a + 1, b])
  165. gr[0, a + 1, b].remove([1, a, b])
  166.  
  167. gr[1, a, b].append([0, a, b])
  168. gr[0, a, b].append([1, a, b])
  169. gr[0, a + 1, b].append([1, a, b + 1])
  170. gr[1, a, b + 1].append([0, a + 1, b])
  171.  
  172. dfs_update((0, a, b), (0, a, b), (), cycletype[0, a, b])
  173.  
  174.  
  175. # print(kolcik)
  176. # print(out - min(kolcik, k) - 2 - n - m)
  177. # if(kolcik)
  178. with open('output.txt', 'w') as f:
  179. f.write(str(out - min(kolcik, k)))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement