Placing Rooks
Time limit1sMemory limit128 MB
Place as many rooks as possible on an N by N board with pawns so no two share a row or column without a pawn between them.
Problem
A rook moves along its own row or column to any square it can reach. Two rooks capture each other when they share a row or a column with nothing in between.
Placing as many non capturing rooks as possible on an empty N × N board is easy. Put one on each square of a diagonal, N in total.
Now add pawns. A rook cannot move through the square a pawn stands on, so a row or a column can hold several rooks as long as a pawn sits between them. Given a board with pawns on it, find the largest number of rooks that can be placed so that no two of them capture each other.
A rook is placed only on an empty square.
Input
The first line contains the board size N. (1 ≤ N ≤ 100)
Each of the next N lines contains one string of length N. A '.' is an empty square and an 'X' is a square with a pawn on it.
Output
Print the largest number of rooks that can be placed.