''' https://www.codingame.com/ide/18267536aa85810c92273263bca743a4f379f708 @author: olinox14, 2019 ''' import sys def log(*msg): print(*msg, file=sys.stderr) rows = [list(input()) for _ in range(int(input()))] cols = [[r[i] for r in rows] for i in range(len(rows))] # for y, r in enumerate(rows): # log("".join(r)) class XInterval(): def __init__(self, y, xstart, xend=-1): self.y = y self.xstart = xstart self.xend = xend self.cells = [] def __repr__(self): return f"" def __len__(self): return self.xend - self.xstart def update(self): self.cells = [(x, self.y) for x in range(self.xstart, self.xend)] class YInterval(): def __init__(self, x, ystart, yend=-1): self.x = x self.ystart = ystart self.yend = yend self.cells = [] def __repr__(self): return f"" def __len__(self): return self.yend - self.ystart def update(self): self.cells = [(self.x, y) for y in range(self.ystart, self.yend)] xintervals = [] for y, row in enumerate(rows): current = XInterval(y, 0) for x, c in enumerate(row): if c == "X": if x > current.xstart: current.xend = x current.update() xintervals.append(current) current = XInterval(y, x + 1) if current.xstart < len(row): current.xend = len(row) current.update() xintervals.append(current) yintervals = [] for x, col in enumerate(cols): current = YInterval(x, 0) for y, c in enumerate(col): if c == "X": if y > current.ystart: current.yend = y current.update() yintervals.append(current) current = YInterval(x, y + 1) if current.ystart < len(col): current.yend = len(col) current.update() yintervals.append(current) graph = [[any(c in yi.cells for c in xi.cells) for xi in xintervals] for yi in yintervals] def bpm(graph, u, matchR, seen): for v in range(len(xintervals)): if graph[u][v] and seen[v] == False: seen[v] = True if matchR[v] == -1 or bpm(graph, matchR[v], matchR, seen): matchR[v] = u return True return False def count_rooks(graph): matchR = [-1 for _ in xintervals] result = 0 for i in range(len(yintervals)): seen = [False for _ in xintervals] if bpm(graph, i, matchR, seen): result += 1 return result print(count_rooks(graph))