huring
0%

51nod-1919-炮兵阵地

Posted on Edited on In

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

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

样例解释：

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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;
}