当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2237:Can 1 Marine win 2 Zerglings?

题目描述
HQM likes StarCraft very much, especially micro-controling. In a difficult micro-control map, he is requested to control 1 marine to defeat 2 zerglings. Although he is a very good player, he still has difficulty to pass the game. So he asks you to find a way to win the game.

The map is a 5*5 matrix, and every square is movable or unmovable. A unit, including the marine and the zergling, can only stay in a movable square. The 2 zerglings can be in the same square but at any time the marine can't stay in the same square with an undead zergling.

Both marine and zerglings have healthy point (we call it HP). When the game start, the marine's HP is m (1 <= m <= 16) and the zerlings' HP are both z (1 <= z <= 99).

The game may be regard as a round style game, in each round, the marine takes action first, and he can choose to move left, right, up or down. But the square he moves to must be movable and contain no alive zergling. The marine may also choose to attack, but in this condition the marine cannot move. He may choose an alive zergling and shoot at it, and every shoot will reduce the HP of the target by 1 (The marine cannot attack 2 zerglings even the two zergling are in the same square). If a zergling's HP less than 1, it will die. After the marine's action, all the alive zerglings will take action. If a zergling is in the square next to the marine's square, it will attack the marine, otherwise it will move follow the shortest way from its position to the marine's position. If there are many shortest ways, it will accord to the following order: left, up, right and down. If there is no way to reach marine, the zergling will not change its position. If the two zerglings are in the same square, their attacks will only reduce the marine's HP by 1,otherwise every zergling's attack will reduce the marine's HP by 1.

If after a round the zerglings are all killed, the player will win the game. But if the marine is killed or the marine can't kill the zerglings in 34 rounds (It is the Time Limit of the map), the player will lose. Now it's your job to determine whether the player can win or not. If he will win, how many rounds he will need at least?
输入解释
In the first 5 lines each contains 5 chars, referring to the map. '1' means the square is unmovable, other chars mean the square is movable, 'M' means the position of the marine, 'Z' and 'z' means the positions of two zerglings. The squares where the marine and zerglings stay at first are also movable. The sixth line of the input contains two integers m and z, refering to the HP of the marine and the zerglings.
输出解释
If the player can win the game, print "WIN" in the first line, and print the rounds needed at least in the second line, otherwise print "LOSE" in a single line.
输入样例
zZ000
11110
00M10
01110
00000
15 15
输出样例
WIN 
30

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 POJ Monthly,HQM

源链接: POJ-2237

最后修改于 2020-10-29T06:27:19+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000 65536