题目描述

HQM 非常喜欢《星际争霸》，尤其是微操（micro-control）。在一张高难度微操地图中，他需要控制 1 个机枪兵（Marine） 击败 2 个跳虫（Zergling）。虽然他是一名优秀的玩家，但仍然难以通关，因此他请你帮忙找到获胜的方法。

地图规则

• 地图是一个 $5 \times 5$ 的矩阵，每个格子要么是 可移动的，要么是 不可移动的。
• 单位（机枪兵或跳虫）只能停留在可移动的格子上。
• 两个跳虫可以站在同一格，但机枪兵 不能 与存活的跳虫站在同一格。

生命值（HP）

• 游戏开始时，机枪兵的 HP 为 $m$（$1 \leq m \leq 16$），两个跳虫的 HP 均为 $z$（$1 \leq z \leq 99$）。

回合制规则

1. 机枪兵的行动（先手）：

   • 移动：可以 向上、下、左、右 移动一格（目标格子必须可移动且没有存活的跳虫）。
   • 攻击：选择 一个存活的跳虫 进行攻击，使其 HP 减 1（不能同时攻击两个跳虫）。如果跳虫 HP $\leq 0$，则死亡。
   • 注意：攻击后 不能移动。

2. 跳虫的行动（后手）：

   • 攻击：如果跳虫 与机枪兵相邻（上下左右），则攻击机枪兵，使其 HP 减 1。
     • 如果两个跳虫在同一格，只扣 1 HP；否则，每个跳虫各扣 1 HP。
   • 移动：如果跳虫 不攻击，则沿 最短路径 向机枪兵移动（优先顺序：左、上、右、下）。
   • 无法移动：如果没有路径到达机枪兵，则跳虫不动。

胜负判定

• 胜利条件：所有跳虫 HP $\leq 0$。
• 失败条件：
  • 机枪兵 HP $\leq 0$。
  • 超过 34 回合（地图时间限制）。

输入格式

• 前 5 行：每行 5 个字符，表示地图：
  • '1'：不可移动的格子。
  • 其他字符：可移动的格子。
  • 'M'：机枪兵的初始位置。
  • 'Z' 或 'z'：两个跳虫的初始位置。
• 第 6 行：两个整数 $m$ 和 $z$，表示机枪兵和跳虫的初始 HP。

输出格式

• 如果玩家能获胜，输出：

  WIN
  <最少回合数>
  

• 否则，输出：

  LOSE
  

示例输入 1

zZ000
11110
00M10
01110
00000
15 15

示例输出 1

WIN
30

题目来源

POJ Monthly, HQM