「一本通 5.4 练习 2」炮兵阵地

形式化题目

给定 $N \times M$ （ $N \le 100$ ， $M \le 10$ ）的网格地图，格子为山地 H 或平原 P。炮兵只能部署在平原上，攻击范围为沿横、纵方向各两格。求互不攻击条件下最多能部署的炮兵数量。

正解

思路

1. 单行合法状态

炮兵左右攻击距离为 2，因此同一行内任意两个炮兵的列间距必须大于 2。用二进制掩码表示一行的部署，合法条件是：

相邻 1 位不冲突：mask & (mask << 1) == 0；
间隔 1 位的 1 不冲突：mask & (mask << 2) == 0。

对 $M \le 10$ ，满足条件的状态最多只有 60 种（远小于 $2^{10} = 1024$ ），可以全部枚举。此外，每行的部署还不能压在山地 H 上，即 state & hill_mask == 0。

2. 行间相容：回看两行

炮兵纵向攻击距离也为 2，所以第 $r$ 行的状态 $s_2$ 必须同时与上一行 $s_1$ 、上上一行 $s_0$ 同列无冲突：

s_2 \& s_1 = 0 \quad \text{且} \quad s_2 \& s_0 = 0

斜方向不在攻击范围内，无需检查。

3. 滚动 DP

设 $dp[(s_0, s_1)]$ 表示上上一行状态为 $s_0$ 、上一行状态为 $s_1$ 时已部署的最大炮兵数。转移时枚举当前行候选状态 $s_2$ （不压山地、与 $s_1, s_0$ 同列不冲突）：

dp'[(s_1, s_2)] = \max\left(dp'[(s_1, s_2)],\ dp[(s_0, s_1)] + \mathrm{cnt}(s_2)\right)

其中 $\mathrm{cnt}(s_2)$ 是 $s_2$ 的置位数（该行炮兵数）。答案为所有行处理完后 $dp$ 中的最大值。

关键规模：状态对 $(s_0, s_1)$ 至多 $60 \times 60 = 3600$ 组合，行数 $N \le 100$ ，总转移量在 $100 \times 3600 \times 60 \approx 2 \times 10^7$ 以内，Python 用字典滚动即可通过。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:38
# update_at: 2026-10-04 11:39

import sys


def is_row_valid(mask: int) -> bool:
    """判断单行内炮兵间距是否均大于 2：左右两格内不能有其他炮兵。"""
    return not (mask & (mask << 1)) and not (mask & (mask << 2))


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    if not tokens:  # 空输入直接结束，保持原有行为
        return
    data = iter(tokens)
    n, m = int(next(data)), int(next(data))  # 行数 n、列数 m
    rows = [next(data).decode() for _ in range(n)]  # 每行的地形串（P/H）
    hill_masks: list[int] = [
        sum((1 if ch == "H" else 0) << (m - 1 - col) for col, ch in enumerate(row))
        for row in rows
    ]

    # 单行无冲突的基准状态集合（M <= 10 时最多仅 60 种）
    valid_states: list[int] = [mask for mask in range(1 << m) if is_row_valid(mask)]
    cannon_counts: dict[int, int] = {mask: mask.bit_count() for mask in valid_states}

    # dp[(s_prev2, s_prev1)]: 上上一行状态为 s_prev2、上一行状态为 s_prev1 时的最大炮兵数
    dp: dict[tuple[int, int], int] = {(0, 0): 0}

    for row_hills in hill_masks:
        nxt: dict[tuple[int, int], int] = {}
        # 当前行候选：不能与山地重合
        candidates = [s for s in valid_states if not (s & row_hills)]
        for (s0, s1), total in dp.items():
            for s2 in candidates:
                if not (s2 & s1) and not (s2 & s0):
                    pair = (s1, s2)
                    new_val = total + cannon_counts[s2]
                    if new_val > nxt.get(pair, -1):
                        nxt[pair] = new_val
        dp = nxt

    print(max(dp.values(), default=0))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:23
 * update_at: 2026-10-05 11:23
 */

#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXN = 105;   // 行数上限
const int MAXM = 10;    // 列数上限，状态压缩按 M<=10
const int MAXS = 70;    // 单行合法状态数（M<=10 时最多 60 种）

int n, m;                       // 网格行数、列数
int hillMask[MAXN];             // hillMask[i]：第 i 行山地的列掩码（H 为 1）
ll numState;                    // 单行合法状态总数
ll states[MAXS];                // states[i]：第 i 个单行合法状态（行内间距 > 2）
ll stateCnt[MAXS];              // stateCnt[i]：该状态的置位数，即该行炮兵数
ll dp[MAXS][MAXS];              // dp[s1][s2]：上一行状态 s1、当前行状态 s2 时的最大炮兵数
ll tmp[MAXS][MAXS];             // tmp：滚动转移用的临时数组
ll candidateCnt;                // 当前行的候选状态数（不压山地的合法状态）
ll candidates[MAXS];            // candidateCnt 个候选状态的下标

// 判断单行状态是否合法：任意两个炮兵列间距必须大于 2
bool rowValid(ll mask) {
    if (mask & (mask << 1)) return false;   // 相邻两位不能同时有炮兵
    if (mask & (mask << 2)) return false;   // 间隔一位也不能同时有炮兵
    return true;
}

// 统计掩码中 1 的个数
ll countBits(ll x) {
    ll c = 0;
    while (x > 0) {
        c += x & 1;
        x >>= 1;
    }
    return c;
}

void solve() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        char row[MAXM + 5];
        scanf("%s", row);
        hillMask[i] = 0;
        // 从左到右读入地形，最高位对应第 0 列
        for (int j = 0; j < m; j++) {
            if (row[j] == 'H') hillMask[i] |= 1 << (m - 1 - j);
        }
    }

    // 预处理所有单行合法状态
    numState = 0;
    for (ll mask = 0; mask < (1LL << m); mask++) {
        if (rowValid(mask)) {
            states[numState] = mask;
            stateCnt[numState] = countBits(mask);
            numState++;
        }
    }

    // 初始 DP：前两行都不部署（状态 0），价值 0
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    // 逐行转移：枚举上一行状态 s1、当前行状态 s2
    for (int i = 0; i < n; i++) {
        // 收集当前行的候选状态：合法且不压山地
        candidateCnt = 0;
        for (ll k = 0; k < numState; k++) {
            if ((states[k] & hillMask[i]) == 0) {
                candidates[candidateCnt++] = k;
            }
        }

        memset(tmp, -1, sizeof(tmp));
        for (ll k1 = 0; k1 < numState; k1++) {          // 上一行状态
            for (ll k2 = 0; k2 < numState; k2++) {      // 当前行候选状态
                if (dp[k1][k2] < 0) continue;           // 不可达
                for (ll t = 0; t < candidateCnt; t++) { // 下一行状态
                    ll k3 = candidates[t];
                    ll s2 = states[k2];
                    ll s3 = states[k3];
                    // 纵向攻击距离 2：与当前行、上一行都不能同列冲突
                    if (s3 & s2) continue;
                    if (s3 & states[k1]) continue;
                    ll newVal = dp[k1][k2] + stateCnt[k3];
                    if (newVal > tmp[k2][k3]) tmp[k2][k3] = newVal;
                }
            }
        }
        // 滚动到下一行
        memcpy(dp, tmp, sizeof(dp));
    }

    // 答案为所有状态对中的最大值
    ll ans = 0;
    for (ll k1 = 0; k1 < numState; k1++) {
        for (ll k2 = 0; k2 < numState; k2++) {
            if (dp[k1][k2] > ans) ans = dp[k1][k2];
        }
    }
    printf("%lld\n", ans);
}

int main() {
    solve();
    return 0;
}

复杂度

时间复杂度： $O(N \cdot S^2 \cdot S_{\text{row}})$ ，其中 $S \le 60$ 为单行合法状态数， $S_{\text{row}}$ 为每行不压山地的候选数（ $\le S$ ）。最坏约 $2 \times 10^7$ 次简单运算，配合位运算判相容（ $O(1)$ ），Python 可在时限内完成。
空间复杂度： $O(S^2)$ ，滚动字典只保留最近两行的状态对，最多 3600 项。

总结

炮兵阵地的核心是"攻击距离为 2"带来的两重约束：行内间距 > 2（mask<<1 与 mask<<2 双判），行间回看两行（与 $s_1, s_0$ 同列不冲突）。
$M \le 10$ 使合法行状态压缩到 60 种以内， $(s_0, s_1)$ 状态对规模仅 3600，DP 总量可控。
山地约束通过 state & hill_mask 在候选生成阶段过滤，与相容性检查解耦，实现简洁。