本文共 1487 字，大约阅读时间需要 4 分钟。

题目传送门：

题意：在一个n*n(n<=4)的区域内建造炮塔，炮塔与炮塔不能在同一行和同一列除非中间有城墙阻隔，要你求出最多能建造多少个炮塔。

思路：因为n最大只有4，可以利用dfs全面检索。

#include <iostream>#include <cstring>using namespace std;int n,maxx;char a[10][10];int b[10][10];   //空地为0，城墙为1，炮塔为2。int judge(int x,int y)   //判断能否造塔。{    int z;    if(b[x][y]!=0) return 0;   //判断当前位置是否为空地。    //下面四个循环分别向四个方向（上下左右）检索是否会遇到炮塔。    for(z=x-1;z>=1;z--)         //上    {        if(b[z][y]==1) break;               //如果遇到墙则执行下一个方向的判断，如果遇到炮塔则直接结束返回0。        else if(b[z][y]==2) return 0;    }    for(z=x+1;z<=n;z++)         //下    {        if(b[z][y]==1) break;        else if(b[z][y]==2) return 0;    }    for(z=y-1;z>=1;z--)         //左    {        if(b[x][z]==1) break;        else if(b[x][z]==2) return 0;    }    for(z=y+1;z<=n;z++)         //右    {        if(b[x][z]==1) break;        else if(b[x][z]==2) return 0;    }    return 1;}//利用dfs深度检索，a表示当前可造的塔数。int dfs(int a){    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)        {            if(judge(i,j))            {                b[i][j]=2;                dfs(a+1);                b[i][j]=0;            }        }    }    if(a>maxx)    {        maxx=a;    }    return maxx;}int main(){     while(cin>>n)     {         if(n==0) break;         memset(b,0,sizeof(b));         int i,j;         for(i=1;i<=n;i++)         {             for(j=1;j<=n;j++)             {                 cin>>a[i][j];                 if(a[i][j]=='X') b[i][j]=1;             }         }         maxx=0;         cout<<dfs(0)<<endl;     }}