安装摄像头

Time Limit: 1000 ms

Memory Limit: 65535 ms

[显示标签]

Description

当下,全国各地安全事故时有发生。各大高校对此很是重视。于是,高校安全设施也相应的增加了。其中摄像头的安装对安全稳定的重要性不言而喻。简而言之,为了实时监控某个区域的状况,我们要在某些区域安装摄像头。
为了使问题简单化,将某个区域看成是有若干方格组成的正方形,每堵墙占一个方格,墙会阻碍摄像头的摄像。也许是各大高校过于紧张,他们觉得安装的摄像头越多越好,然而他们又不希望过于浪费(即不希望两个或多个摄像头出现在同一行或同一列)。当然大前提是监控整个区域。 请你帮忙找出可以安装的最大摄像头数。(可以假设,每个摄像头只能监控它所在方格的列和行)。

Input

有多个用例直到文件结尾 每个用例的形式如下: 第一行:n分别表示矩形方格的行数和列数(1<=n<=4) 以下为n*n矩阵。用 “.” 表示空的区域,用“X”表示墙。

Output

一个整数,表示所要安装的最大摄像头数。

Sample Input

4
....
....
....
....
4
.X..
....
XX..
....

Sample Output

4
5

Hint

Source

ShiLuDeng

提交代码