Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # import sys
- # from math import *
- # from copy import copy
- from pprint import pprint
- import pdb
- import sys
- sys.setrecursionlimit(1000000)
- # import itertools
- # from pprint import pprint
- from collections import deque
- # import sys
- f = open('input.txt', 'r')
- # o = open('input.txt', 'w')
- input = sys.stdin.readline
- def print(*args, sep=' ', end='\n'):
- s = ''
- for i in args:
- s += str(i) + sep
- s += end
- sys.stdout.write(s)
- def rI():
- return [int(i) for i in f.readline().split()]
- # print(rI())
- n, m, k = rI()
- idat = [None for i in range(n)]
- for ix in range(len(idat)):
- idat[ix] = list(f.readline().strip()) + ['.']
- idat.append(['.' for i in range(m + 1)])
- gr = {}
- iscycle = {}
- cycletype = {}
- vis = {}
- for i in [0, 1]:
- for a in range(n + 1):
- for b in range(m + 1):
- gr[i, a, b] = []
- vis[i, a, b] = False
- iscycle[i, a, b] = False
- for a in range(n):
- for b in range(m):
- if(idat[a][b] == '.'):
- continue
- if(idat[a][b] == '/'):
- gr[1, a, b].append([0, a, b])
- gr[0, a, b].append([1, a, b])
- gr[0, a + 1, b].append([1, a, b + 1])
- gr[1, a, b + 1].append([0, a + 1, b])
- else:
- gr[0, a, b].append([1, a, b + 1])
- gr[1, a, b + 1].append([0, a, b])
- gr[1, a, b].append([0, a + 1, b])
- gr[0, a + 1, b].append([1, a, b])
- # pprint(gr)
- # pdb.set_trace()
- out = 0
- kolcik = 0
- def dfs(a, st, fr):
- vis[a] = True
- for i in gr[a]:
- i = tuple(i)
- if(i == st) and (st != fr):
- global kolcik
- kolcik += 1
- que = deque()
- que.append(i)
- # pdb.set_trace()
- while(len(que) != 0):
- curr = que.popleft()
- iscycle[curr] = True
- cycletype[curr] = kolcik
- for ii in gr[curr]:
- ii = tuple(ii)
- if(iscycle[ii] == False):
- que.append(ii)
- # print(iscycle[ii])
- return
- if(vis[i] == False):
- dfs(i, st, a)
- for i in [0, 1]:
- for a in range(n + 1):
- for b in range(m + 1):
- # if(idat[a][b] == '.'):
- # continue
- if(vis[i, a, b] == False):
- if(len(gr[i, a, b]) == 0):
- continue
- # print(i, a, b)
- dfs((i, a, b), (i, a, b), ())
- out += 1
- for i in range(n):
- if(len(gr[1, i, m]) == 0):
- continue
- if(vis[1, i, m] == False):
- dfs((1, i, m), (1, i, m), ())
- out += 1
- for i in range(m):
- if(len(gr[0, n, i]) == 0):
- continue
- if(vis[0, n, i] == False):
- dfs((0, n, i), (0, n, i), ())
- out += 1
- pv = 0
- def dfs_update(a, st, fr, typ):
- cycletype[a] = typ
- if(a == st):
- return
- fist = tuple(gr[a][0])
- sec = tuple(gr[a][1])
- if(fr != fist):
- dfs_update(fist, st, a, typ)
- else:
- dfs_update(sec, st, a, typ)
- for a in range(n):
- for b in range(m):
- if(idat[a][b] == '.'):
- continue
- if(k == 0):
- break
- if(iscycle[0, a, b] == True and iscycle[0, a, b + 1] == True):
- if(cycletype[0, a, b] == cycletype[0, a, b + 1]):
- continue
- kolcik -= 1
- out -= 1
- k -= 1
- if(idat[a][b] == '/'):
- gr[1, a, b].remove([0, a, b])
- gr[0, a, b].remove([1, a, b])
- gr[0, a + 1, b].remove([1, a, b + 1])
- gr[1, a, b + 1].remove([0, a + 1, b])
- gr[0, a, b].append([1, a, b + 1])
- gr[1, a, b + 1].append([0, a, b])
- gr[1, a, b].append([0, a + 1, b])
- gr[0, a + 1, b].append([1, a, b])
- else:
- gr[0, a, b].remove([1, a, b + 1])
- gr[1, a, b + 1].remove([0, a, b])
- gr[1, a, b].remove([0, a + 1, b])
- gr[0, a + 1, b].remove([1, a, b])
- gr[1, a, b].append([0, a, b])
- gr[0, a, b].append([1, a, b])
- gr[0, a + 1, b].append([1, a, b + 1])
- gr[1, a, b + 1].append([0, a + 1, b])
- dfs_update((0, a, b), (0, a, b), (), cycletype[0, a, b])
- # print(kolcik)
- # print(out - min(kolcik, k) - 2 - n - m)
- # if(kolcik)
- with open('output.txt', 'w') as f:
- f.write(str(out - min(kolcik, k)))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement