P17191 [ICPC 2017 Hong Kong R] Marine

In a fantastic map of Starcraft, you are required to use one marine to defeat two zerglines. As you do not think whether this mission is possible or not, you have to simulate it with a program. The map consists of $5 \times 5$ grids, and each grid can either be passable or not passable. The marine and zerglings are always in passable grids. Two zerglings may be in the same grid, but the marine can not be in the same grid with any alive zergling in any time. Initially, the health point $(HP)$ of the marine is $m$, and the $HPs$ of both zerglings are $z$. The game runs in turns. In each turn, the game runs in three phases. 1. The marine moves by one grid in horizontal or vertical direction, or do not move to shoot to one zergling. Because the size of the map is small, the marine can shoot to any zergline in any position. The shooting in each turn reduces the HP of the target zergline by $1$. If the HP of a zergline is equal to or less than $0$, it dies. 2. All alive zerglines move at the same time. If a zergline is in the neighbouring grid of the marine, it will attack the marine, otherwise it will move by one grid in the shortest path to the marine. If there are multiple ways, it will choose with priority of left, up, right and down (e.g. if both going left and going up are in the shortest path, it will choose going left). If both zerglings in the same grid and attack the marine, the HP of the marine will be reduced by 1, otherwise each zergling attacks the marine and decreases the HP of the marine by 1. If the $HP$ of the marine is equal to or less than $0$, it dies. 3. The system checks the status of the marine and zerglings. If both zerglings die, you win. If the marine die, you lose. Furthermore, if you can not win the game in $34$ turns, you lose the game. You need to figure out whether if you can win the game or not. If yes, output the minimum turns in which you win the game.

The input file might contains multiple cases, please handle it to the end of file. The first five lines of each case is a map. Each line contains five characters. The meaning of each character is following. * 1: a impassable grid * M: the marin * Z: one zergling * z: another zergling * other characters: passable grids In the six line, there are two integers $m, z(0 < m \le 16, 0 < z \le 99)$, as described above.

For each case, if you can win, output ‘WIN’ in the first line and the minimum turns in the second line, otherwise output ‘LOSE’.

Remark: In the example above, the best strategy is that the marine does not move, and shoots to zerglings ‘Z’ first, and then shoots to ‘z’. The zergling ‘Z’ moves to the neighbouring grid of the marine after turn $14$ but it is killed in turn $15$. The zergling ‘z’ moves to the neighbouring grid of the marine after turn $15$. And then, the zergling ‘z’ and the marine attack each other in the next $15$ turns. In turn $30$, because the marine moves first, it kills zergline ‘z’ and has $1$ $HP$ remained.