冲突
成绩 | 100 | 开启时间 | 2020年02月16日 星期日 20:25 |
折扣 | 0.8 | 折扣时间 | 2020年02月16日 星期日 20:25 |
允许迟交 | 是 | 关闭时间 | 2020年02月16日 星期日 20:25 |
输入文件 | Conflict.in | 输出文件 | Conflict.out |
【题目描述】冲突(Conflict) POJ 1315
监狱的每间牢房是一个不超过4×4的正方形,里面设有一些障碍,牢房里住着的犯人脾气都很大,只要两个犯人位于同一行或同一列即会发生冲突,但障碍物可以阻挡同行或同列犯人的冲突。问最多可放几个犯人而不会发生冲突。如图2.16所示,左边表示初始牢房样,右边显示了四种摆放方案,当然,最后两个方案是错误的。
【输入格式】
有多组测试数据,每组数据第一行为一个整数N表示牢房大小。随后N行“.”描述牢房,“X”表示障碍。
所有测试数据结束的标志为0。
【输出格式】
输出最多可放的犯人数。
【输入样例】
4 (表示牢房大小)
.X.. (“.”描述牢房,“X”表示障碍)
....
XX..
....
3
.X.
X.X
.X.
3
...
.XX
.XX
0
【输出样例】
5
5
2