题解：P17191 [ICPC 2017 Hong Kong R] Marine

· · 题解

题意简述

在 5\times5 的地图上控制一名机枪兵。每回合可以移动一格，或留在原地射击一只存活的跳虫。随后两只跳虫同时攻击或沿指定优先级的最短路移动。求能否在 34 回合内获胜，并输出最少回合数。

解题思路

每回合至多射击一次，两只跳虫一共需要受到 2z 点伤害。因此：

2z>34

时一定无法获胜。后续只需处理 z\le17 的情况，所有位置和跳虫生命值都能用 5 个二进制位保存。

先预处理跳虫的确定性行为。对每个可能的机枪兵位置 p，从 p 开始在可通行格上做 BFS，得到其他格子到 p 的最短距离。对跳虫所在格 x，按照左、上、右、下检查相邻格，第一个距离严格减小的格子就是它本回合的移动目标。若 x 与 p 相邻，则另行标记为攻击，不使用移动表。

按回合进行分层 BFS。忽略机枪兵生命值后，一个状态包含：

两只跳虫的规则与初始属性完全相同，交换它们的全部信息不会改变后续结果。因此，每次存储状态前，都按照 (a,x) 与 (b,y) 的大小关系固定顺序。死亡跳虫的生命值和位置都记为 0。这样可以合并仅由编号交换产生的重复状态。

上述五个量各占 5 位，可以压入一个整数作为哈希键。机枪兵生命值不放入键，而是记录同一 BFS 层、同一键能够保留的最大生命值。

这种支配剪枝不会删除最优方案。相同回合、相同五元状态的全部后续合法动作和跳虫行为完全一致。生命值更高的机枪兵可以照搬生命值更低状态的所有动作，并且不会更早死亡，所以只保留最大值已经足够。

从每个状态枚举六种机枪兵动作：射击第一只跳虫、射击第二只跳虫，以及向四个方向移动。射击已经死亡的目标无效；移动目标必须可通行，也不能与存活跳虫重合。

若射击后两只跳虫都死亡，本回合结束时必然获胜，可以立即返回当前层数加一。否则先根据两只跳虫行动前的位置同时判断攻击：

生命值扣除后若机枪兵死亡，舍弃状态。没有攻击的存活跳虫再分别查表移动。这里必须先完成两只攻击判定，再改变任意一只的位置，才能符合「同时行动」的规则。

设当前已经完成 t+1 回合。若两只跳虫剩余生命值之和大于 34-(t+1)，即使余下每回合都射击也无法获胜，可以直接剪枝。

BFS 第一次产生胜利状态时，所在层数就是最少回合数。搜索完第 34 层仍未获胜，则输出 LOSE。

位置三元组至多有 25^3 种，生命值对至多有 18^2 种，再通过交换对称、生命值支配和剩余射击次数剪枝只保留实际可达状态。每个状态只扩展六种动作，地图预处理规模固定为 25 个格子。

正确性证明

对固定机枪兵位置做 BFS 得到真实最短距离。跳虫依次检查左、上、右、下，并选择第一个使距离减少一的相邻格，恰好实现题目规定的最短路与优先级；相邻时直接攻击也按规则单独处理。因此预处理表准确描述每只跳虫的单回合行为。

搜索枚举了机枪兵能够执行的两类射击与四个方向移动，并检查了通行性和禁止重合条件。射击、同时攻击、伤害合并、死亡判定与未攻击跳虫移动均严格按照一个回合的阶段顺序执行，所以每条搜索边都对应一个合法回合，任何合法回合也会被某条搜索边枚举。

交换两只跳虫只改变名称，不改变位置、生命值和规则，状态规范化保持可行策略集合不变。同层同键的状态中，较高机枪兵生命值能够执行较低生命值状态的全部后续动作，因此最大生命值支配其余状态。两个剪枝都不影响可达性和最少回合数。

分层 BFS 按回合数从小到大枚举全部未被支配的合法状态。第一次击杀两只跳虫时，不存在回合数更少而尚未处理的方案。剩余伤害大于剩余回合数的状态不可能完成任务，删除也不会损失答案。因此算法输出的胜利回合数最小；若没有输出，确实不存在 34 回合内的获胜策略。

参考代码

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

const int N=30;
const int inf=0x3f3f3f3f;
const int dx[4]={0,-1,0,1};
const int dy[4]={-1,0,1,0};
string s[5];
bool ok[N],hit[N][N];
int go[N][4],nxt[N][N];
void norm(int &x,int &y,int &a,int &b)
{
    if(a>b||(a==b&&x>y))
    {
        swap(x,y);
        swap(a,b);
    }
}
int get_key(int p,int x,int y,int a,int b)
{
    norm(x,y,a,b);
    return p|(x<<5)|(y<<10)|(a<<15)|(b<<20);
}
void prepare()
{
    for(int i=0;i<25;i++)
    {
        for(int j=0;j<4;j++)
        {
            int x=i/5+dx[j],y=i%5+dy[j];
            go[i][j]=x>=0&&x<5&&y>=0&&y<5&&ok[x*5+y]?x*5+y:-1;
        }
    }
    for(int i=0;i<25;i++)
    {
        int dis[N];
        fill(dis,dis+N,inf);
        queue<int>que;
        dis[i]=0;
        que.push(i);
        while(que.size())
        {
            int x=que.front();
            que.pop();
            for(int j=0;j<4;j++)
            {
                int y=go[x][j];
                if(y<0||dis[y]<=dis[x]+1)continue;
                dis[y]=dis[x]+1;
                que.push(y);
            }
        }
        for(int j=0;j<25;j++)
        {
            hit[i][j]=abs(i/5-j/5)+abs(i%5-j%5)==1;
            nxt[i][j]=j;
            for(int k=0;k<4;k++)
            {
                int x=go[j][k];
                if(x<0||dis[x]>=dis[j])continue;
                nxt[i][j]=x;
                break;
            }
        }
    }
}
int solve(int p,int x,int y,int m,int z)
{
    if(z*2>34)return -1;
    unordered_map<int,int>f,g;
    f.reserve(1<<19);
    g.reserve(1<<19);
    f.max_load_factor(0.7);
    g.max_load_factor(0.7);
    f[get_key(p,x,y,z,z)]=m;
    for(int k=0;k<34;k++)
    {
        g.clear();
        for(auto [key,hp]:f)
        {
            p=key&31;
            x=(key>>5)&31;
            y=(key>>10)&31;
            int a=(key>>15)&31,b=(key>>20)&31;
            for(int i=0;i<6;i++)
            {
                int np=p,nx=x,ny=y,na=a,nb=b;
                if(i<2)
                {
                    int &h=i?nb:na;
                    int &q=i?ny:nx;
                    if(!h)continue;
                    if(!--h)q=0;
                }
                else
                {
                    np=go[p][i-2];
                    if(np<0||(na&&np==nx)||(nb&&np==ny))continue;
                }
                if(!na&&!nb)return k+1;
                bool u=na&&hit[np][nx],v=nb&&hit[np][ny];
                int nhp=hp-u-v+(u&&v&&nx==ny);
                if(nhp<=0)continue;
                if(na&&!u)nx=nxt[np][nx];
                if(nb&&!v)ny=nxt[np][ny];
                if(na+nb>33-k)continue;
                int nkey=get_key(np,nx,ny,na,nb);
                auto j=g.find(nkey);
                if(j==g.end()||j->second<nhp)g[nkey]=nhp;
            }
        }
        f.swap(g);
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while(cin>>s[0]>>s[1]>>s[2]>>s[3]>>s[4])
    {
        int p,x,y;
        for(int i=0;i<5;i++)
        {
            for(int j=0;j<5;j++)
            {
                int k=i*5+j;
                ok[k]=s[i][j]!='1';
                if(s[i][j]=='M')p=k;
                if(s[i][j]=='Z')x=k;
                if(s[i][j]=='z')y=k;
            }
        }
        int m,z;
        cin>>m>>z;
        prepare();
        int ans=solve(p,x,y,m,z);
        if(ans<0)cout<<"LOSE"<<'\n';
        else cout<<"WIN"<<'\n'<<ans<<'\n';
    }
    return 0;
}