解题思路

这是一道基于 BFS 的最短路径问题，需考虑以下关键点：

状态表示：玩家的位置 (x, y) 和时间 t，其中 t 需记录到每个状态的最短时间。 怪物位置计算：根据时间 t 和怪物的位置序列，计算每个怪物在 t 时刻的位置及攻击范围。 移动合法性判断： 玩家移动后的位置不能是岩石、怪物占据的单元格。 若怪物是攻击性的，需检查玩家是否在其攻击范围内。 BFS 剪枝：若到达某位置的时间已大于等于之前记录的最短时间，跳过该状态。 边界条件：时间超过 100 秒时直接判定为失败。

步骤：

解析输入：提取地图信息、玩家起点、宝藏位置、怪物初始位置及移动序列。 预处理怪物序列：为每个怪物生成循环的位置列表，便于快速查询 t 时刻的位置。 BFS 初始化：从玩家起点出发，时间 t=0，记录已访问的位置和时间。 每步 BFS 处理： 计算当前时间 t 下所有怪物的位置及攻击范围。 生成玩家的所有可能移动（停留、行走、奔跑），检查每个移动是否合法。 若到达宝藏位置，返回当前时间 t+1（因移动耗时 1 秒）。 处理多组测试用例：注意输入中的空行分隔，输出结果也需用空行分隔。 #cpp #include #include #include #include <unordered_map> #include #include #include using namespace std;

// 方向定义：行走方向（8方向）和奔跑方向（8方向，步长2） const vector<pair<int, int>> dirs_walk = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}; const vector<pair<int, int>> dirs_run = {{-2, -2}, {-2, 0}, {-2, 2}, {0, -2}, {0, 2}, {2, -2}, {2, 0}, {2, 2}};

struct Monster { vector<pair<int, int>> path; // 位置序列 int idx; // 当前路径索引 };

struct State { int x, y, time; State(int x, int y, int t) : x(x), y(y), time(t) {} };

// 地图信息 int n, m; vector grid; pair<int, int> start, treasure; vector monsters; // 存储所有怪物信息 vector is_aggressive; // 标记是否为攻击性怪物

// 检查坐标是否在地图范围内 bool isValid(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

// 获取t时刻怪物的位置 pair<int, int> getMonsterPos(int monster_idx, int t) { int s = monsters[monster_idx].path.size(); int pos_idx = t % s; return monsters[monster_idx].path[pos_idx]; }

// 检查玩家在(x,y)是否安全（怪物移动后） bool isSafe(int x, int y, int t) { // 检查是否被怪物占据或在攻击性怪物的攻击范围内 for (int i = 0; i < monsters.size(); ++i) { auto [mx, my] = getMonsterPos(i, t); if (mx == x && my == y) return false; // 被怪物占据 if (is_aggressive[i]) { // 检查是否在攻击范围（周围8格） for (auto [dx, dy] : dirs_walk) { int nx = mx + dx, ny = my + dy; if (nx == x && ny == y) return false; } if (mx == x && my == y) return false; // 自身位置 } } return true; }

// 检查移动路径是否合法（玩家移动时） bool checkPath(int sx, int sy, int ex, int ey, int t) { // 处理行走：直接检查终点 if (abs(ex - sx) <= 1 && abs(ey - sy) <= 1) { return grid[ex-1][ey-1] != '#' && isSafe(ex, ey, t); } // 处理奔跑：检查中间点和终点 int dx = ex - sx, dy = ey - sy; if (abs(dx) != 2 || abs(dy) != 2) return false; // 非对角线奔跑 int mid_x = sx + dx/2, mid_y = sy + dy/2; // 中间点是否可通行，且终点合法 return grid[mid_x-1][mid_y-1] != '#' && grid[ex-1][ey-1] != '#' && isSafe(ex, ey, t); }

int bfs() { queue q; vector<vector> dist(n+1, vector(m+1, INT_MAX)); // 记录最短时间 int start_x, start_y, treasure_x, treasure_y; tie(start_x, start_y) = start; tie(treasure_x, treasure_y) = treasure;

q.push(State(start_x, start_y, 0));
dist[start_x][start_y] = 0;

while (!q.empty()) {
    State curr = q.front();
    q.pop();
    
    if (curr.x == treasure_x && curr.y == treasure_y) {
        return curr.time;
    }
    if (curr.time >= 100) continue; // 超过时间限制
    
    int t = curr.time + 1; // 下一时刻
    // 计算所有怪物在t时刻的位置（移动后）
    // 生成所有可能的移动：停留、行走、奔跑
    vector<pair<int, int>> moves;
    moves.push_back({curr.x, curr.y}); // 停留
    for (auto [dx, dy] : dirs_walk) { // 行走
        int nx = curr.x + dx, ny = curr.y + dy;
        moves.push_back({nx, ny});
    }
    for (auto [dx, dy] : dirs_run) { // 奔跑
        int nx = curr.x + dx, ny = curr.y + dy;
        moves.push_back({nx, ny});
    }
    
    for (auto [nx, ny] : moves) {
        if (!isValid(nx, ny)) continue;
        if (!checkPath(curr.x, curr.y, nx, ny, t)) continue;
        if (dist[nx][ny] <= t) continue; // 已有更短路径
        dist[nx][ny] = t;
        q.push(State(nx, ny, t));
    }
}
return -1; // 无法到达

}

void solve() { bool first_case = true; while (true) { cin >> n >> m; if (n == 0 && m == 0) break; if (!first_case) cout << endl; first_case = false;

    grid.clear();
    start = {-1, -1};
    treasure = {-1, -1};
    vector<pair<int, int>> monster_positions; // 记录初始怪物位置（按行优先）
    
    for (int i = 0; i < n; ++i) {
        string line;
        cin >> line;
        grid.push_back(line);
        for (int j = 0; j < m; ++j) {
            if (line[j] == 'p') {
                start = {i+1, j+1};
            } else if (line[j] == 't') {
                treasure = {i+1, j+1};
            } else if (line[j] == 'a' || line[j] == 'n') {
                monster_positions.push_back({i+1, j+1});
            }
        }
    }
    
    // 解析怪物信息
    monsters.clear();
    is_aggressive.clear();
    int p;
    cin >> p;
    for (int i = 0; i < p; ++i) {
        int s;
        cin >> s;
        vector<pair<int, int>> path(s);
        for (int j = 0; j < s; ++j) {
            int x, y;
            cin >> x >> y;
            path[j] = {x, y};
        }
        monsters.push_back({path, 0});
        // 根据初始位置判断是否为攻击性怪物（初始位置在monster_positions中的顺序）
        // 假设monster_positions中的顺序与输入中的怪物顺序一致（按行优先）
        is_aggressive.push_back(grid[monster_positions[i].first-1][monster_positions[i].second-1] == 'a');
    }
    
    // 处理空行（可能存在连续测试用例间的空行）
    string empty_line;
    while (getline(cin, empty_line) && empty_line.empty());
    
    int result = bfs();
    if (result == -1 || result > 100) {
        cout << "impossible";
    } else {
        cout << result;
    }
}

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }