n × m 平原（n ≤ 100, m ≤ 10），每格 1 可駐兵、0 不可。士兵攻擊範圍為曼哈頓距離 ≤ 2 的格子（含自身）。士兵不可站在互相攻擊範圍內。求最大駐兵數。
曼哈頓距離 ≤ 2 意味著：同格、上下左右相鄰、對角線相鄰、同行/列間隔一格。即同行相鄰列、同列相鄰行、對角線、間隔一格同行/列均衝突。
逐行 DP，狀態為當前行駐兵情況（m ≤ 10，狀態數 ≤ 1024）。合法狀態需滿足：
map[row][col] == 1）放置。void dfs(int row, int col, int state, int cnt) {
if (col >= m) {
validStates[row].push_back({state, cnt});
return;
}
// 選擇放兵：需地形允許、前兩列無兵
if (map[row][col] && (col < 2 || !(state & (1 << (col-2))))) {
dfs(row, col+1, state | (1<當前行狀態 cur、上一行 pre、上上行 ppre 需滿足：
cur & ppre == 0：間隔一行同列衝突。cur & (pre << 1) == 0：當前行與上一行左偏一列衝突（對角線/曼哈頓距離 2）。cur & (pre >> 1) == 0：當前行與上一行右偏一列衝突。注意：同列相鄰行（cur & pre）已被行內間隔條件隱含禁止（因同列相鄰行距離 1 ≤ 2）。
dp[i][j]：第 i 行狀態 j 時，前 i 行最大駐兵數。為了 O(1) 轉移，維護 best[pre][ppre] 表示上一行 pre、上上行 ppre 的最大值。
for (int i = 0; i < n; ++i) {
for (auto &cur : validStates[i]) {
for (auto &pre : validStates[i-1]) {
for (auto &ppre : validStates[i-2]) {
if (conflict(cur.state, pre.state, ppre.state)) continue;
dp[cur][pre] = max(dp[cur][pre], best[pre][ppre] + cur.cnt);
}
}
}
// 更新 best 供下一行使用
for (auto &cur : validStates[i])
for (auto &pre : validStates[i-1])
best[cur][pre] = dp[cur][pre];
}
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct State { int mask, cnt; };
int n, m;
int map[105][15];
vector<State> validStates[105];
int dp[1<<10][1<<10], best[1<<10][1<<10];
bool conflict(int cur, int pre, int ppre) {
if (cur & ppre) return true;
if (cur & (pre << 1)) return true;
if (cur & (pre >> 1)) return true;
return false;
}
void genStates(int row) {
validStates[row].clear();
function<void(int,int,int)> dfs = [&](int col, int mask, int cnt) {
if (col >= m) { validStates[row].push_back({mask, cnt}); return; }
if (map[row][col] && (col < 2 || !(mask & (1<<(col-2)))))
dfs(col+1, mask | (1< 1) {
for (auto &cur : validStates[1])
for (auto &pre : validStates[0])
if (!conflict(cur.mask, pre.mask, 0))
dp[cur.mask][pre.mask] = max(dp[cur.mask][pre.mask], best[pre.mask][0] + cur.cnt);
for (auto &cur : validStates[1])
for (auto &pre : validStates[0])
best[cur.mask][pre.mask] = dp[cur.mask][pre.mask];
}
// 第 2 行及以後
for (int i = 2; i < n; ++i) {
memset(dp, 0, sizeof(dp));
for (auto &cur : validStates[i])
for (auto &pre : validStates[i-1])
for (auto &ppre : validStates[i-2])
if (!conflict(cur.mask, pre.mask, ppre.mask))
dp[cur.mask][pre.mask] = max(dp[cur.mask][pre.mask], best[pre.mask][ppre.mask] + cur.cnt);
for (auto &cur : validStates[i])
for (auto &pre : validStates[i-1])
best[cur.mask][pre.mask] = dp[cur.mask][pre.mask];
}
int ans = 0;
for (int i = 0; i < (1< F_{m+2}（費波納契數），m=10 時約 144 個。O(n * S^3)，實際 S ≈ 100，n=100 約 106 操作，極快。dp[1024][1024] 約 4MB，best 同樣，符合限制。conflict()，避免重複位運算。
