P17191 [ICPC 2017 Hong Kong R] Marine

在一张星际争霸的奇妙地图上，你需要用一个机枪兵击败两只跳虫。由于你并不关心这个任务是否可能完成，你必须用一个程序来模拟它。 地图由 $5 \times 5$ 的网格组成，每个网格要么可通行，要么不可通行。机枪兵和跳虫始终位于可通行的网格中。两只跳虫可以处于同一个网格，但机枪兵在任何时候都不能与任何存活的跳虫处于同一格。初始时，机枪兵的生命值（HP）为 $m$，两只跳虫的生命值均为 $z$。 游戏按回合进行。每个回合分为三个阶段。 1. 机枪兵沿水平或垂直方向移动一格，或不移动而向某一只跳虫开火。由于地图尺寸很小，机枪兵可以向任意位置的跳虫射击。每回合射击会使目标跳虫的生命值减少 $1$。若一只跳虫的生命值降至 $0$ 或以下，它将死亡。 2. 所有存活的跳虫同时移动。如果某只跳虫位于机枪兵的相邻格子，它会攻击机枪兵；否则它将沿最短路径向机枪兵移动一格。如果存在多条最短路径，它会按照左、上、右、下的优先级顺序选择（例如，向左走和向上走都在最短路径上时，它会选择向左走）。若两只跳虫在同一格子且攻击机枪兵，机枪兵的生命值将减少 $1$；否则每只跳虫各自攻击机枪兵，各自使机枪兵生命值减少 $1$。若机枪兵的生命值降至 $0$ 或以下，它将死亡。 3. 系统检查机枪兵和跳虫的状态。若两只跳虫均死亡，你获胜。若机枪兵死亡，你失败。此外，如果你不能在 $34$ 个回合内获胜，你也将失败。 你需要判断是否能赢得游戏。若能，输出你赢得游戏所需的最少回合数。

输入可能包含多个测试用例，请处理到文件结尾。每个用例的前五行是地图，每行包含五个字符。各字符的含义如下。 * `1`：不可通行的格子 * `M`：机枪兵 * `Z`：一只跳虫 * `z`：另一只跳虫 * 其他字符：可通行的格子 第六行包含两个整数 $m, z$（$0 < m \le 16$，$0 < z \le 99$），含义如上所述。

对于每个用例，若能获胜，第一行输出 `WIN`，第二行输出最少回合数；否则输出 `LOSE`。

注意：在上面的例子中，最佳策略是机枪兵不移动，先射击跳虫 ‘Z’，再射击跳虫 ‘z’。跳虫 ‘Z’ 在 $14$ 回合后移动到机枪兵的相邻格子，但在第 $15$ 回合被击杀。跳虫 ‘z’ 在 $15$ 回合后移动到机枪兵的相邻格子。随后，跳虫 ‘z’ 和机枪兵在接下来的 $15$ 回合中相互攻击。在第 $30$ 回合，因为机枪兵先行动，它击杀了跳虫 ‘z’ 并剩余 $1$ 点生命值。 翻译由 DeepSeek V4 Pro 完成