51nod-1919-炮兵阵地

题目： 司令部的将军们打算在N*N的网格地图上部署他们的炮兵部队。一个N*N的地图由N行N列组成，地图的每一格可能是山地（用"X"表示），也可能是平原（用".“表示）。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围是它所在位置的对应的行和列，但是大炮打出去之后如果被山地阻挡 了，那么攻击范围就到那块山地。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

样例解释：

上图中显示的是相同的地图中不同的放置大炮的方案。黑方块表示山地，白方块表示平原，黑圆表示对应的平原放置了大炮。第一张图是不放大炮的情况。第二张图和第三张图是合理的放置大炮的方案。最后两张图是不合理的放置大炮的方案。 对于这个地图来讲，最多能放置5门大炮。第二张图就是一种最优的放置方案，当然还有其它的最优放置方案。

输入 单组测试数据。 第一行有一个整数N(1<=N<=4)。 接下来N行，每行有N个字符（只有两种字符：’.’ 表示平原， ‘X’表示山地）。 输出 输出一个整数表示答案。 输入样例 样例输入1 4 .X.. …. XX.. …. 输出样例 样例输出1 5 解法：因此数据极小，因此暴力每次情况即可，最终选取可放置数量最多的。 代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;
char c[5][5];
char s[5][5];
void change(int x)
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++){
            if(c[i][j] == '.'){
                if(x&1)
                    s[i][j] = 'p';
                else{
                    s[i][j] = '.';
                }
            }
            else{
                s[i][j] = 'X';
            }
            x >>= 1;
        }
}
bool isTrue()
{
    for(int i = 0; i < n ;i++)
    {
        int now = 0;
        for(int j = 0; j < n; j++){
            if(s[i][j] == 'p')
                now++;
            else if(s[i][j] == 'X'){
                now = 0;
            }
            if(now > 1)
                return false;
        }
    }
    for(int i = 0; i < n ;i++)
    {
        int now = 0;
        for(int j = 0; j < n; j++){
            if(s[j][i] == 'p')
                now++;
            else if(s[j][i] == 'X'){
                now = 0;
            }
            if(now > 1)
                return false;
        }
    }
    return true;
}
int ans()
{
        int num = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                if(s[i][j] == 'p')
                    num++;
    return num;
}
int main()
{
    scanf("%d\n", &n);
    char t;
    for(int i = 0; i < n ;i++){
        for(int j = 0; j < n; j++)
            scanf("%c", &c[i][j]);
        scanf("%c", &t);
    }

    int now = 1;
    now <<= n*n+1;
    now--;
    //printf("%d\n", now);
    int ANS = 0;
    while(now--)
    {
        change(now);
        if(isTrue()){
            ANS = max(ANS, ans());
        }
    }
    printf("%d\n", ANS);
    return 0;
}