《算法竞赛宝典》基础算法艺术(公开课程)

【题目描述】冲突(Conflict.cpp/c/pas) POJ 1315

监狱的每间牢房是一个不超过4×4的正方形，里面设有一些障碍，牢房里住着的犯人脾气都很大，只要两个犯人位于同一行或同一列即会发生冲突，但障碍物可以阻挡同行或同列犯人的冲突。问最多可放几个犯人而不会发生冲突。如图2.18所示，左边表示初始牢房样，右边4个显示了摆放方案，当然，最后两个方案是错误的。

【输入格式】

有多组测试数据，每组数据第一行为一个整数Ｎ表示牢房大小。随后Ｎ行描述牢房，其中X表示障碍。

所有测试数据结束的标志为０。

【输出格式】

输出最多可放的犯人数。

【输入样例】

4　　（表示牢房大小）

.X..　（描述牢房，Ｘ表示障碍）　

....

XX..

....

3

.X.

X.X

.X.

3

...

.XX

.XX

0　　（表示结束）

【输出样例】

5

5

2