codeingame/puzzle_rook.py

'''
    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"<XI({self.xstart}, {self.y})-({self.xend}, {self.y})>"
    
    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"<YI({self.x}, {self.ystart})-({self.x}, {self.yend})>"
    
    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))