Hi i need a bit of help !
Consider a chessboard of size NxN.
Your must find the maximum number of bishops that can be placed on the chessboard, such that no pair of bishops can attack each other. Some cells are damaged. Bishops cannot be placed on these cells, but they can attack through them. N<100
I can do a naive bruteforce but it keeps giving me timelimit. Any tip how to optimize it ?
Thanks!
It is maximal matching problem.
Let's build a graph:
Diagonals will be its vertices
There is an edge between two vertices if their diagonals share a cell.
We have to build maximum matching in this bicomponent graph.
It can be done with Hungarian algorithm in O(n3) time.