题解

解题思路

这是一个典型的回合制策略游戏问题，可以通过状态空间搜索（BFS）来解决：

1. 状态表示：

   • 记录机枪兵和两个跳虫的位置
   • 记录各单位的当前HP值
   • 记录当前回合数

2. 状态转移：

   • 机枪兵回合：
     • 移动：尝试四个方向的移动（不能与跳虫重叠）
     • 攻击：如果相邻跳虫存在，选择攻击
   • 跳虫回合：
     • 自动攻击相邻的机枪兵
     • 使用BFS计算最短路径向机枪兵移动

3. 剪枝优化：

   • 使用哈希表记录已访问状态，避免重复计算
   • 超过34回合或机枪兵HP≤0时提前终止

4. 路径寻找：

   • 使用BFS为跳虫计算到机枪兵的最短路径
   • 移动时按照左、上、右、下的优先级选择方向

代码

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <climits>

using namespace std;

struct Position {
    int x, y;
    Position(int x = -1, int y = -1) : x(x), y(y) {}
    bool operator<(const Position& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
    bool operator==(const Position& other) const {
        return x == other.x && y == other.y;
    }
};

struct GameState {
    Position marine;
    Position zergling1, zergling2;
    int marineHP, zergling1HP, zergling2HP;
    int turns;
    bool operator<(const GameState& other) const {
        if (marineHP != other.marineHP) return marineHP < other.marineHP;
        if (zergling1HP != other.zergling1HP) return zergling1HP < other.zergling1HP;
        if (zergling2HP != other.zergling2HP) return zergling2HP < other.zergling2HP;
        if (!(marine == other.marine)) return marine < other.marine;
        if (!(zergling1 == other.zergling1)) return zergling1 < other.zergling1;
        return zergling2 < other.zergling2;
    }
};

vector<string> grid(5);
int marineHP, zerglingHP;
Position marinePos, zergling1Pos(-1, -1), zergling2Pos(-1, -1);
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右

bool isValid(int x, int y) {
    return x >= 0 && x < 5 && y >= 0 && y < 5 && grid[x][y] != '1';
}

bool isAdjacent(const Position& a, const Position& b) {
    return abs(a.x - b.x) + abs(a.y - b.y) == 1;
}

void findShortestPath(const Position& start, const Position& target, vector<vector<int> >& dist) {
    queue<Position> q;
    dist.assign(5, vector<int>(5, INT_MAX));
    dist[start.x][start.y] = 0;
    q.push(start);

    while (!q.empty()) {
        Position current = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dirs[i][0];
            int ny = current.y + dirs[i][1];

            if (isValid(nx, ny)) {
                if (dist[nx][ny] > dist[current.x][current.y] + 1) {
                    dist[nx][ny] = dist[current.x][current.y] + 1;
                    q.push(Position(nx, ny));
                }
            }
        }
    }
}

Position getNextMove(const Position& zergling, const Position& marine) {
    vector<vector<int> > dist;
    findShortestPath(zergling, marine, dist);

    if (dist[marine.x][marine.y] == INT_MAX) {
        return zergling; // 没有路径
    }

    Position bestMove = zergling;
    int minDist = INT_MAX;

    // 检查四个方向，按左、上、右、下的优先级
    for (int i = 2; i >= 0; --i) { // 左(2)、上(0)、右(3)
        int nx = zergling.x + dirs[i][0];
        int ny = zergling.y + dirs[i][1];

        if (isValid(nx, ny)) {
            if (dist[nx][ny] < minDist) {
                minDist = dist[nx][ny];
                bestMove = Position(nx, ny);
            }
        }
    }
    
    // 检查下方向(1)
    int nx = zergling.x + dirs[1][0];
    int ny = zergling.y + dirs[1][1];
    if (isValid(nx, ny) && dist[nx][ny] < minDist) {
        bestMove = Position(nx, ny);
    }

    return bestMove;
}

int solve() {
    queue<GameState> q;
    map<GameState, int> visited;

    GameState initial;
    initial.marine = marinePos;
    initial.zergling1 = zergling1Pos;
    initial.zergling2 = zergling2Pos;
    initial.marineHP = marineHP;
    initial.zergling1HP = zerglingHP;
    initial.zergling2HP = zerglingHP;
    initial.turns = 0;

    q.push(initial);
    visited[initial] = 0;

    while (!q.empty()) {
        GameState current = q.front();
        q.pop();

        // 胜利条件检查
        if (current.zergling1HP <= 0 && current.zergling2HP <= 0) {
            return current.turns;
        }

        // 失败条件检查
        if (current.turns >= 34 || current.marineHP <= 0) {
            continue;
        }

        // 机枪兵的回合 - 移动选项
        for (int i = 0; i < 4; ++i) {
            int nx = current.marine.x + dirs[i][0];
            int ny = current.marine.y + dirs[i][1];

            if (isValid(nx, ny)) {
                bool z1Alive = current.zergling1HP > 0;
                bool z2Alive = current.zergling2HP > 0;
                bool z1Here = z1Alive && current.zergling1.x == nx && current.zergling1.y == ny;
                bool z2Here = z2Alive && current.zergling2.x == nx && current.zergling2.y == ny;

                if (!z1Here && !z2Here) {
                    GameState next = current;
                    next.marine = Position(nx, ny);
                    next.turns++;

                    if (visited.find(next) == visited.end() || next.turns < visited[next]) {
                        visited[next] = next.turns;
                        q.push(next);
                    }
                }
            }
        }

        // 机枪兵的回合 - 攻击选项
        if (current.zergling1HP > 0 && isAdjacent(current.marine, current.zergling1)) {
            GameState next = current;
            next.zergling1HP--;
            next.turns++;

            if (visited.find(next) == visited.end() || next.turns < visited[next]) {
                visited[next] = next.turns;
                q.push(next);
            }
        }

        if (current.zergling2HP > 0 && isAdjacent(current.marine, current.zergling2)) {
            GameState next = current;
            next.zergling2HP--;
            next.turns++;

            if (visited.find(next) == visited.end() || next.turns < visited[next]) {
                visited[next] = next.turns;
                q.push(next);
            }
        }

        // 跳虫的回合
        GameState afterZerglings = current;
        afterZerglings.turns++;

        // 跳虫攻击
        bool z1Attacked = false, z2Attacked = false;
        if (afterZerglings.zergling1HP > 0 && isAdjacent(afterZerglings.marine, afterZerglings.zergling1)) {
            afterZerglings.marineHP--;
            z1Attacked = true;
        }
        if (afterZerglings.zergling2HP > 0 && isAdjacent(afterZerglings.marine, afterZerglings.zergling2)) {
            // 如果两个跳虫在同一格且已经攻击过，不再重复攻击
            if (!(afterZerglings.zergling1 == afterZerglings.zergling2 && z1Attacked)) {
                afterZerglings.marineHP--;
            }
            z2Attacked = true;
        }

        // 跳虫移动
        if (!z1Attacked && afterZerglings.zergling1HP > 0) {
            afterZerglings.zergling1 = getNextMove(afterZerglings.zergling1, afterZerglings.marine);
        }
        if (!z2Attacked && afterZerglings.zergling2HP > 0) {
            afterZerglings.zergling2 = getNextMove(afterZerglings.zergling2, afterZerglings.marine);
        }

        if (visited.find(afterZerglings) == visited.end() || afterZerglings.turns < visited[afterZerglings]) {
            visited[afterZerglings] = afterZerglings.turns;
            q.push(afterZerglings);
        }
    }

    return -1;
}

int main() {
    // 读取地图
    for (int i = 0; i < 5; ++i) {
        cin >> grid[i];
        for (int j = 0; j < 5; ++j) {
            if (grid[i][j] == 'M') {
                marinePos = Position(i, j);
            } else if (grid[i][j] == 'Z' || grid[i][j] == 'z') {
                if (zergling1Pos.x == -1) {
                    zergling1Pos = Position(i, j);
                } else {
                    zergling2Pos = Position(i, j);
                }
            }
        }
    }

    // 读取HP
    cin >> marineHP >> zerglingHP;

    int result = solve();
    if (result != -1) {
        cout << "WIN" << endl << result << endl;
    } else {
        cout << "LOSE" << endl;
    }

    return 0;
}

复杂度分析

• 时间复杂度：O(5×5×HP³×34)，最坏情况下需要探索所有可能的状态
• 空间复杂度：O(5×5×HP³)，用于存储已访问状态

代码实现要点

1. 数据结构：

   • Position结构体存储坐标
   • GameState结构体存储游戏状态（位置、HP、回合数）

2. 核心函数：

   • getNextMove()：计算跳虫的下一步移动
   • solve()：BFS主循环处理状态转移

3. 输入处理：

   • 读取5x5地图，识别初始位置
   • 读取机枪兵和跳虫的初始HP