
ZOJ Problem Set  3695
A huge wave of fat sheeps is coming! This time, plants have travelled to planet 218. They have heard the fat sheeps here had won the Alevel Chinese Meals championship in Universe Final. Certainly they won't miss the chance to taste this meal! Now, all what they need to do is to lay an ambush for those tasty sheeps... But before laying an ambush, we need to know the environment here clearly. You can assume that planet 218 is a rectangle containing N*M grids. Grids may have different terrains. Here are four kinds of terrains, including:
Here are two kinds of plants that can cook sheeps, including:
And now all plants can be upgraded! Each plant has a basic energy cost Ri, a basic attacking speed Si (which means plant i can attack Si times in a minute), a basic damage Ti on level 1. If a plant spend Ui more energy, it upgrades a level, and it will receive Vi bonus attacking speed and Wi bonus damage each level. Certainly, it has a max level Li (the initial level is level 1). Now, P sheeps is coming. Each sheep will occupy 1 grid and have Hi hit points (HP). Each sheep will appear at minute Gi, and if two sheeps are standing on the same grid, they will be attacked simultaneously. Only when a sheep's HP is lower or equal to 0 will it be cooked. And, They will just run in the shortest path (which means, the time cost is minimal) towards the end without any pause or retreat. If there exist more than 1 shortest path, choose the one with the minimal alphabet order, if we express the path with N,S,E,W (N for North, S for South, E for East, W for West). The whole planet has 1 start and 1 exit on different grids to sheeps' home only, and the terrain of the start and the exit will always be a plain. Sheeps will spend 1 minute on the start and exit as well. There will be at least 1 path between the start and the end. Plants can grow in an instant at any time. Plants want to know the minimal energy it will cost to cook all sheeps. Will any fat sheeps avoid this doom? InputThe input contains less than 30 test cases. The first line contains two integer N, M, P (1 ≤ N, M ≤ 32 , 1 ≤ P ≤ 1024). Following N lines contain M characters each, indicating the map, with '.' stands for plains, 'x' stands for stones, 'k' stands for knolls, and 'w' stands for wetlands. Specially, 's' stands for start, and 't' stands for the exit. Next line include P integers Hi (1 ≤ Hi ≤ 1024), indicating the HP of each sheep. Next line include P integers Gi (0 ≤ Gi ≤ 1024), indicating the appearing time of each sheep. Following a line contains the R1, S1 ,T1 ,U1 ,V1 ,W1 ,L1 (1 ≤ R1, U1 ≤ 100, 0≤ S1, T1, V1, W1 ≤ 100, 1 ≤ L1 ≤ 5) of Fire Pea. Following a line contains the R2, S2 ,T2 ,U2 ,V2 ,W2 ,L2, X (1 ≤ R2, U2 ≤ 100, 0≤ S2, T2, V2, W2 ≤ 100, 1 ≤ L2 ≤ 5, 1 ≤ X ≤ 5) of Fumeshroom. OutputFor each test case, output a line with an integer, indicating the minimal cost if plants can cook all sheeps. If not, output "Happy summer holiday!".Sample Input4 5 1 .wwx. s.... .kkw. ....t 5 0 4 1 4 3 1 1 2 5 1 0 1 1 1 2 2 3 3 4 wxk swx .tw 1 2 3 4 1 2 3 4 1 5 5 1 5 5 5 1 5 5 1 5 5 5 1 Sample Output6 Happy summer holiday! HintIn case 1, the route is "EEEESS", because it only takes 7 minutes, and compared to "SSEEEE", it has the minimal alphabet order. You can plant an level 2 Fumeshroom on any grid of knolls. That plant's speed is 2 and damage is 1. It can cook the sheep when the sheep walks around it for 3 minutes. It cost 6 energy. In case 2, none of the plants can hit sheeps. Author: LIN, Jinghao Contest: ZOJ Monthly, March 2013 