描述 城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙，其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔，则两个堡垒都会把对方打掉。问对于给定的一种状态，最多能够修建几个堡垒。
输入 每个测例以一个整数n（1<=n<=4）开始，表示城堡的大小。接下来是n行字符每行n个，‘X’表示该位置是墙，‘.’表示该位置是空格。n等于0标志输入结束。
输出 每个测例在单独的一行输出一个整数：最多修建堡垒的个数。
输入样例 4 .X… … XX… … 2 XX .X 3 .X. X.X .X. 3 … .XX .XX 4 … … … … 0
输出样例 5 1 5 2 4
思路：穷举所有可能的且尽可能多放置堡垒的排列方式，计算每一次所放置的堡垒数，取最大值。
代码如下：
#include <iostream> using namespace std; int q[100][100];//记录地图，0表示空格，1表示已放置堡垒，2表示墙 int n;//n阶地图 int max0;//最多放置的堡垒数目 int x;//每次排列所得的堡垒数 int cun[100];//存储每个max0的结果 int r;//有r组数据 bool Place(int i,int j)//判断是否能放置堡垒 { if(q[i][j]==2)return false;//如果该位置是墙 int k1,k2; for(k2=j-1;k2>=0;k2--){//判断该点左路 if(q[i][k2]==2)break; if(q[i][k2]==1)return false; } for(k2=j+1;k2<=n;k2++){//判断该点右路 if(q[i][k2]==2)break; if(q[i][k2]==1)return false; } for(k1=i-1;k1>=0;k1--){//判断该点上路 if(q[k1][j]==2)break; if(q[k1][j]==1)return false; } for(k1=i+1;k1<=n;k1++){//判断该点下路 if(q[k1][j]==2)break; if(q[k1][j]==1)return false; } return true; } void f1()//计算放置堡垒数目的最大值 { int i,j; x=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(q[i][j]==1){ x++; } }//计算当次所放置的堡垒数 if(max0<x)max0=x;//与之前计算的最大值比较 } void f(int i,int j)//核心递归函数，判断所有位置是否能放堡垒 { if(i>n){//如果每个位置都判断完，即得到一次结果，调用f1 f1(); } else{//还没判断完全部的方格 for(;j<=n;j++){//在一行里的每一个位置判断 if(Place(i,j)){ q[i][j]=1;//满足要求放置堡垒 f(i,j+1);//继续寻找同一行的下一个位置 q[i][j]=0;//*****回溯***** } } f(i+1,1);//第i行找完则转入下一行查找，从第(i+1)行的第一列开始 } } void Output()//输出 { int i; for(i=0;i<r;i++)cout<<cun[i]<<endl; } void Cun()//存储每组的最大值 { cun[r]=max0; r++; } void f2()//将地图全部置为空 { int i,j; for(i=0;i<=n+1;i++)//所用地图从i=1到i=n，但为了Place函数的判断，初始化时候需要多包围地图一圈 for(j=0;j<=n+1;j++){ q[i][j]=0; } } void f3()//输入地图 { char wall[100][100]; int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ cin>>wall[i][j]; if(wall[i][j]=='X'){//q[i][j]=2,置为墙 q[i][j]=2; } } } int main() { r=0;//已经计算了r组数据 cin>>n; for(;n;){ max0=0;//每一组数据计算前最大值为0 f2(); f3(); f(1,1);//不用下标为0的数组,从第一个位置q[1][1]开始判断 Cun(); cin>>n; } Output(); return 0; }运行结果：
