HDU 4499 Cannon：暴力枚舉行狀態（位掩碼）+ 剪枝 DFS 放置最大炮數

問題描述

n × m (n,m ≤ 5) 棋盤，已有 k 個棋子（不可移動）。炮的攻擊規則：同行/同列中間恰好有一個棋子（作為炮架）才能攻擊。求最多能再放置多少個炮，使炮之間互不攻擊（現有棋子不算炮，但可作炮架）。

解法：逐行枚舉狀態 + 位掩碼 + DFS 剪枝

• m ≤ 5，每行狀態可用 5 位二進制數表示（0~31）。預先篩選合法行狀態：炮數 ≤ 3（因每行最多 3 炮才能互不攻擊）。
• DFS 逐行嘗試所有合法狀態：

1. 檢查與現有棋子是否衝突（state & board[row] == 0）。
2. 放置後檢查新炮是否與左側、上方已放炮攻擊：掃描左/上方向，遇到第一個棋子/炮作為炮架，若再遇炮則攻擊，非法。
3. 遞歸下一行，回溯時恢復棋盤。
4. 剪枝：若 當前炮數 + 剩餘行數 × 3 ≤ 最優解 剪枝。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;

int n, m, k;
int board[MAXN][MAXN];
vector validStates;
int ans = 0;

int bitCount(int x) { return x ? bitCount(x>>1) + (x&1) : 0; }

void genStates() {
    for (int s = 0; s < (1<= 0; --c) {
        if (flag && board[row][c] == 2) return true;
        if (flag && board[row][c] == 1) return false;
        if (board[row][c]) flag = 1;
    }
    // 向上
    flag = 0;
    for (int r = row-1; r >= 0; --r) {
        if (flag && board[r][col] == 2) return true;
        if (flag && board[r][col] == 1) return false;
        if (board[r][col]) flag = 1;
    }
    return false;
}

bool judgeRow(int row) {
    for (int c = 0; c < m; ++c)
        if (board[row][c] == 2 && checkAttacks(row, c)) return false;
    return true;
}

void dfs(int row, int cnt) {
    if (ans >= cnt + (n - row) * 3) return; // 剪枝
    if (row == n) { ans = max(ans, cnt); return; }
    for (int s : validStates) {
        if (!checkRow(row, s)) continue;
        setRow(row, s, 2);
        if (judgeRow(row)) dfs(row+1, cnt + bitCount(s));
        setRow(row, s, 0);
    }
}

int main() {
    genStates();
    while (scanf("%d%d%d", &n, &m, &k) == 3) {
        memset(board, 0, sizeof(board));
        for (int i = 0; i < k; ++i) {
            int x, y; scanf("%d%d", &x, &y);
            board[x][y] = 1; // 1 代表原有棋子
        }
        ans = 0;
        dfs(0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

狀態數 ≤ 32，n ≤ 5，搜索空間極小，瞬間通過。