---------------------------------------------------------------------------------------------------------------------------
严格来讲，此题并不算我做出来的。因为我在WA后忍不住搜索了这道题的网上资料，并在参考了“洞庭散人”的代码后AC的。
----------------------------------------------------------------------------------------------------------------------------
ZOJ 1002： Fire Net（碉堡 火力网）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=2
此题大意是在一个最大4*4网格组成的城市里，每个网格可能为“墙壁”（用‘X’表示）和“街道”（用‘.’表示）。现在在街道放置碉堡，每个碉堡可以向上下左右四个方向开火，子弹射程无限远。墙壁可以阻挡子弹。问最多能放置多少个碉堡，使它们彼此不会互相摧毁。
例如输入：
.X..
....
XX..
....
则应输出最大个数为5。
此题和n后问题非常类似，因此可用回溯法搜索整个解空间树。最开始我使用了“贪心法”但是WA，原因就在于贪心法的特点是：得到的解不一定是整体最优解。因此还是得用回溯法搜索整个空间树。和n后问题解法一样，CanPut是判别函数，判断位置（x，y）是否能放置碉堡。
以下是我写的代码，但大体上都参考了洞庭散人的文章（代码在本质上完全一致）：
http://www.cnblogs.com/phinecos/archive/2008/09/18/1293017.html
Code_1002_Fire_Net
/*ZOJ 1002 - Fire Net */
/*n最大为4，使用回溯法搜索解空间树*/
#include <stdio.h>
char map[4][5];
int maxCount;/*最多可放置碉堡数*/
/* 测试（x，y）位置是否可以放置碉堡 */
int CanPut(int n, int x, int y)
{
/*因为行列是递增的，因此只需向上和向左搜索是否有碉堡即可*/
int i;
/*向左推移, 0表示不能被占用*/
i=x;
while(i>0 && map[i-1][y]!='X')
if (map[--i][y]=='O') return 0;
/*向上*/
i=y;
while(i>0 && map[x][i-1]!='X')
if(map[x][--i]=='O') return 0;
/*可以放置*/
return 1;
}
/*找出最大碉堡树, n是city的尺寸，k是距离起始点的一维长度距离*/
void Search(int n, int k, int curCount)
{
int x,y;
if(k==n*n)
{
/*arrived the bottom*/
if(curCount>maxCount)
maxCount=curCount;
return;
}
else
{
x=k/n;
y=k%n;
if(map[x][y]=='.' && CanPut(n,x,y))
{
/*该点可以放置，则进入该分支*/
map[x][y]='O';/*put a houseblock*/
Search(n, k+1, curCount+1);
/*回退*/
map[x][y]='.';
}
/*向下一个分支*/
Search(n,k+1,curCount);
}
}
int main()
{
int n,i,count;
while(scanf("%d",&n)!=EOF && n>0)
{
for(i=0;i<n;i++)
scanf("%s", map[i]);
maxCount=0;
Search(n, 0, 0);
printf("%d\n",maxCount);
}
}