提示: 欢迎访问OurACM平台。
Problem 1401 死亡迷宫

Accept: 76    Submit: 413
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

背景

很久以前,迷宫里住着一个恶魔。一天,我们伟大的英雄Andy无意中踏入了这个迷宫。不幸的是,他被困在这个迷宫当中了。恶魔在迷宫中召唤出了许多怪物,想要阻止Andy逃脱。 在迷宫中,Andy遇到一个一位巫师。他给了Andy迷宫的地图,并告诉他迷宫的入口很快会关闭。Andy必须以非常快的速度到达入口,并且有足够的力气推开挡在入口的岩石。于是,Andy带着地图一路向着出口走去……

问题

给出Andy和各怪物的能量, 攻击力, 防御力,和迷宫的地图,请你计算一下 能量/耗时 的最大值。

当Andy走到有怪物的地方时,Andy会先进行攻击,然后怪物攻击,然后Andy……当一方的能量小于等于0时攻击停止,并且小于等于0的一方死亡。攻击时,每次对方损耗的能量为己方的攻击力减去对方的防御力。

当Andy走到标有‘A’,‘B’,‘C’的地方时,Andy的相应属性会得到增加。

对应关系如下:

[A] 能量 + P [B] 攻击力 + Q [C] 防御力 + R

如果耗时超过100,那么门将永远也打不开了,我们的Andy也就永远的困在了这个暗无天日的迷宫之中……

输入

标准输入包含多组数据。

每组数据的第一行有六个整数W (1 <= W <= 20), H (1 <= H <= 20), P (1 <= P <= 10), Q (1<= Q <= 10), R (1 <= R <= 10), M (0 <= M <= 5). 迷宫是由一个W*H的矩形区域构成。M表示怪物的数量。Andy每个单位时间可以移动到相邻的4个格中,当然,必须得保证目标格在矩形区域中。默认的起始时间是0。与怪物战斗不会花费额外的时间。

其后H行每行严格包含W个字符。用如下的各字符表示这个迷宫的地图:

[#]表示一堵墙(Andy是不会穿墙术的) [.] Marks an empty space, into which you can move.表示一块空地。 [S]表示Andy的初始位置。 [E]表示迷宫的入口。 [0]表示各怪物。 [A]表示属性增加地点。(使用次数仅限于一次)

其后一行有三个整数,表示Andy的能量,攻击力,和防御力。

其后M行,每行有四个整数,表示怪物的编号,和这个怪物的各属性。

Input

标准输入包含多组数据。

每组数据的第一行有六个整数W (1 <= W <= 20), H (1 <= H <= 20), P (1 <= P <= 10), Q (1<= Q <= 10), R (1 <= R <= 10), M (0 <= M <= 5). 迷宫是由一个W*H的矩形区域构成。M表示怪物的数量。Andy每个单位时间可以移动到相邻的4个格中,当然,必须得保证目标格在矩形区域中。默认的起始时间是0。与怪物战斗不会花费额外的时间。

其后H行每行严格包含W个字符。用如下的各字符表示这个迷宫的地图:

[#]表示一堵墙(Andy是不会穿墙术的)
[.] Marks an empty space, into which you can move.表示一块空地。
[S]表示Andy的初始位置。
[E]表示迷宫的入口。
[0]表示各怪物。
[A]表示属性增加地点。(使用次数仅限于一次)

其后一行有三个整数,表示Andy的能量,攻击力,和防御力。

其后M行,每行有四个整数,表示怪物的编号,和这个怪物的各属性。

Output

对于每组输入数据,输出 能量/耗时 的最大值,并保留4位小数。如果Andy不能到达出口,输出“impossible”。数据之间无空行。

Sample Input

6 17 7 5 4 3 ################# ##E......#......# #A#....#.0.##.#B# #1###########2### #.S............C# ################# 100 59 10 0 23 48 0 1 65 41 0 2 20 27 0

Sample Output

3.7037

Source

Andy Zhau's Contest No.1

Submit  Back  Status  Discuss