（题解由ai整理，部分代码也经过了ai调试优化）

问题分析

这是一个回合制博弈问题，目标是用最少回合让 Marine 击败两只 Zergling。由于需要找 最少回合数，广度优先搜索（BFS）是最佳选择（BFS 按层遍历，首次到达胜利状态的步数即为最小值）。

核心思路

1. 状态设计

用结构体 State 记录完整局面：
- Marine：位置 (mx, my)、血量 mhp
- Zergling：两只的位置 (zx[2], zy[2])、血量 zhp[2]

关键优化：两只 Zergling 无差别，需对其排序（normalize 函数），避免将「Zerg1在A、Zerg2在B」和「Zerg1在B、Zerg2在A」视为不同状态，防止状态爆炸。

2. BFS 框架

• 队列：存储 (状态, 步数)，按回合顺序扩展
• 访问标记：用 set<State> 记录已搜索状态，避免重复

3. 回合流程

每个回合严格按以下顺序执行：

（1）Marine 行动（二选一）

• 移动：尝试上下左右 4 个方向，需满足：
  • 在 5×5 地图内
  • 不是障碍（字符 '1'）
  • 不与存活的 Zergling 重叠
• 攻击：选择一只存活的 Zergling，使其血量 -1（可攻击地图任意位置）

（2）Zergling 行动（同时执行）

• 攻击判定：若 Zergling 与 Marine 相邻（上下左右），则攻击，记录攻击者位置
• 伤害计算：
  • 1 只攻击：伤害 +1
  • 2 只攻击：若在同一格，伤害 +1；若在不同格，伤害 +2
• 移动规则：不攻击的 Zergling 沿最短路向 Marine 移动，方向优先级为 左、上、右、下（需用 BFS 预计算每个方向的最短距离）

4. 终止条件

• 胜利：两只 Zergling 血量 ≤ 0，返回当前步数
• 失败：步数 > 34 或 Marine 血量 ≤ 0，继续搜索其他分支

代码关键点

1. 状态归一化：对 Zergling 按 (是否死亡, x, y, hp) 排序，确保状态唯一
2. 方向优先级：严格按左、上、右、下的顺序遍历方向
3. 伤害计算：根据攻击者位置是否相同区分伤害值
4. 最短路计算：用 BFS 计算 Zergling 移动时每个方向的下一步到 Marine 的距离

复杂度说明

• 状态空间：Marine 位置 25 种，血量 16 种；Zergling 位置约 25×25 种，血量各 99 种。经归一化后状态数可控，BFS 可在 1 秒内完成。

这个思路通过 BFS 保证最少步数，结合状态归一化和细节处理（伤害、移动优先级），即可正确解决问题。

#include <bits/stdc++.h>
using namespace std;

const int N = 5;
const int dx[5] = {0, -1, 0, 1, 0}; // 0:占位, 1:上, 2:左, 3:右, 4:下
const int dy[5] = {0, 0, -1, 0, 1};

struct State {
    int mx, my, mhp;
    int zx[2], zy[2], zhp[2];
    
    bool operator<(const State& o) const {
        return tie(mx, my, mhp, zx[0], zy[0], zhp[0], zx[1], zy[1], zhp[1]) <
               tie(o.mx, o.my, o.mhp, o.zx[0], o.zy[0], o.zhp[0], o.zx[1], o.zy[1], o.zhp[1]);
    }
    
    void normalize() {
        auto key0 = make_tuple(zhp[0] <= 0, zx[0], zy[0], zhp[0]);
        auto key1 = make_tuple(zhp[1] <= 0, zx[1], zy[1], zhp[1]);
        if (key1 < key0) {
            swap(zx[0], zx[1]);
            swap(zy[0], zy[1]);
            swap(zhp[0], zhp[1]);
        }
    }
};

char a[10][10];
int m, z;
set<pair<int, int>> block;

bool inmap(int x, int y) {
    return x >= 1 && x <= N && y >= 1 && y <= N;
}

int bfs_dist(int sx, int sy, int tx, int ty, const set<pair<int, int>>& block) {
    queue<pair<int, int>> q;
    int vis[10][10] = {};
    q.push({sx, sy});
    vis[sx][sy] = 1;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) return vis[x][y] - 1;
        for (int d = 1; d <= 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!inmap(nx, ny)) continue;
            if (block.count({nx, ny})) continue;
            if (!vis[nx][ny]) {
                vis[nx][ny] = vis[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return 1000;
}

void process_zergling(State& ns, int& dmg) {
    int n_zx[2], n_zy[2], n_zhp[2];
    for (int j = 0; j < 2; ++j) {
        n_zx[j] = ns.zx[j];
        n_zy[j] = ns.zy[j];
        n_zhp[j] = ns.zhp[j];
    }
    
    vector<pair<int, int>> attackers;
    for (int j = 0; j < 2; ++j) {
        if (n_zhp[j] <= 0) continue;
        bool adj = false;
        for (int d2 = 1; d2 <= 4; ++d2) {
            if (n_zx[j] + dx[d2] == ns.mx && n_zy[j] + dy[d2] == ns.my) {
                adj = true; break;
            }
        }
        if (adj) attackers.emplace_back(n_zx[j], n_zy[j]);
    }
    
    dmg = 0;
    if (attackers.size() == 1) dmg = 1;
    else if (attackers.size() == 2) {
        dmg = (attackers[0] == attackers[1]) ? 1 : 2;
    }
    
    int dir_order[] = {2, 1, 3, 4};
    for (int j = 0; j < 2; ++j) {
        if (n_zhp[j] <= 0) continue;
        bool is_attacking = false;
        for (auto& p : attackers) {
            if (p.first == n_zx[j] && p.second == n_zy[j]) {
                is_attacking = true; break;
            }
        }
        if (is_attacking) continue;
        
        int min_dist = 1000;
        int best_dir = -1;
        for (int d2 : dir_order) {
            int tx = n_zx[j] + dx[d2], ty = n_zy[j] + dy[d2];
            if (!inmap(tx, ty)) continue;
            if (block.count({tx, ty})) continue;
            if (tx == ns.mx && ty == ns.my) continue;
            int dist = bfs_dist(tx, ty, ns.mx, ns.my, block);
            if (dist < min_dist) {
                min_dist = dist;
                best_dir = d2;
            }
        }
        if (best_dir != -1) {
            n_zx[j] += dx[best_dir];
            n_zy[j] += dy[best_dir];
        }
    }
    
    for (int j = 0; j < 2; ++j) {
        ns.zx[j] = n_zx[j];
        ns.zy[j] = n_zy[j];
        ns.zhp[j] = n_zhp[j];
    }
}

int solve(State start) {
    queue<pair<State, int>> Q;
    set<State> vis;
    start.normalize();
    Q.push({start, 0});
    
    while (!Q.empty()) {
        auto [s, step] = Q.front(); Q.pop();
        
        if (step > 34 || s.mhp <= 0) continue;
        if (s.zhp[0] <= 0 && s.zhp[1] <= 0) return step;
        if (vis.count(s)) continue;
        vis.insert(s);
        
        for (int d = 1; d <= 4; ++d) {
            int nx = s.mx + dx[d], ny = s.my + dy[d];
            if (!inmap(nx, ny)) continue;
            if (block.count({nx, ny})) continue;
            bool ok = true;
            for (int i = 0; i < 2; ++i) {
                if (s.zhp[i] > 0 && nx == s.zx[i] && ny == s.zy[i]) {
                    ok = false; break;
                }
            }
            if (!ok) continue;
            
            State ns = s;
            ns.mx = nx; ns.my = ny;
            int dmg = 0;
            process_zergling(ns, dmg);
            ns.mhp -= dmg;
            ns.normalize();
            Q.push({ns, step + 1});
        }
        
        for (int i = 0; i < 2; ++i) {
            if (s.zhp[i] <= 0) continue;
            State ns = s;
            ns.zhp[i]--;
            int dmg = 0;
            process_zergling(ns, dmg);
            ns.mhp -= dmg;
            ns.normalize();
            Q.push({ns, step + 1});
        }
    }
    return -1;
}

int main() {
    for (int i = 1; i <= 5; ++i) cin >> (a[i] + 1);
    cin >> m >> z;
    State start;
    int zcnt = 0;
    for (int i = 1; i <= 5; ++i) {
        for (int j = 1; j <= 5; ++j) {
            if (a[i][j] == 'M' || a[i][j] == 'm') {
                start.mx = i; start.my = j; start.mhp = m;
            } else if (a[i][j] == 'Z' || a[i][j] == 'z') {
                start.zx[zcnt] = i; start.zy[zcnt] = j; start.zhp[zcnt] = z;
                ++zcnt;
            } else if (a[i][j] == '1') {
                block.insert({i, j});
            }
        }
    }
    for (; zcnt < 2; ++zcnt) {
        start.zx[zcnt] = start.zy[zcnt] = -1;
        start.zhp[zcnt] = 0;
    }
    int ans = solve(start);
    if (ans != -1) {
        cout << "WIN\n" << ans << endl;
    } else {
        cout << "LOSE" << endl;
    }
    return 0;
}

好长的DP程序！！！！！！

Accepted 有效得分：100 有效耗时：172ms

floyd+DP+模拟=AC~~

（虽然有点慢.....）

楼下有误！

对于同一个枪兵的位置，相同的HP，狗的位置并不是唯一的。

N楼下给出一个很好的反例：

00000

11111

00011

z101Z

00M00

14 8

比较猥琐的方法是加一维：一只狗的位置。

比较好的方法是用hash表。

预处理出点对点的最短路径的方向

用BFS

判重时只要记录 枪兵的位置 枪兵HP 两只狗的HP

因为狗的位置是由人的位置决定，所以无需记录

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

简单要死

這個小狗偷盜雷獸巢科技升了5級甲麽 = =

记忆化搜索过了

这题范围小所以数组可以尽量开

打到手酸

题主提示看到这道题，我们就会想到贪心。贪心有两种A. 根本不移动，原地攻击，不成功，便成仁反例：000000111z00ZM0111100000011 5原地不动会被包夹致死。正解请自己研究。B. 分为移动和攻击两个阶段。移动阶段只移动，攻击阶段只原地攻击。这个算法是对贪心A打了一个小补丁。刚才的反例固然解决了，能否保证最优呢？反例：000001111100011z101Z00M0014 8如果第一步向左或右移动一格，就白白被逼近一格。如果不移动，就会被包夹致死。正解请自己研究。贪心就被否决了，又难以建立好的图论模型。只能采取搜索和动态规划了。题主通过的程序就是使用动态规划。一个小小小小小小优化：大家会发现zergling HP 99大得有点突尤。其实，当2*zergling HP大于回合数时，任务必然失败。

解题方案谁有

看星星的好地方---|-屋顶

好不容易

先弄个天花板