Submit solution

Points: 15
Time limit: 11.0s
Memory limit: 64M

Author:
Problem type
University of Toronto ACM-ICPC Tryouts 2012

It's down to the final match in the world's biggest SC21 tournament! You're the MVP2 of MVP3, and you're going up against MVP4. There are G (1 \le G \le 20) games in the series, with a winner decided after all have been played. Being a Protoss5 player, you know the perfect way to win against that Terran6 scum - with a cannon rush7 every single game. Now you just have to execute it perfectly, by quickly getting your probe10 to the correct location, and the prize money's sure to be yours.

Each game will take place on a map which can be represented as a grid with H (2 \le H \le 1\,000) rows of W (2 \le W \le 1\,000) cells each. Each cell contains either empty space (represented by E), water (W), a unit (U), one of exactly two mineral patches (M), the probe (P), or the cannon rush site (C). Every second, your probe can move to a horizontally- or vertically-adjacent cell within the grid, with the goal of reaching the cannon rush site in as little time as possible. It can move freely from an empty cell to another empty cell (including its initial position and destination), while cells containing water or minerals may never be traversed.

Normally, the probe may also not pass through units. However, it can if it is travelling towards a mineral patch. Specifically, the probe can only leave or enter a cell containing a unit if, for at least one of the two mineral patches on the map, the cell which the probe is entering is closer to that patch than the cell which the probe is leaving. Closeness is defined according to the minimum amount of time it would take to reach the mineral patch from the given cell, assuming the ability to pass through all units on the way.

For each game, you'd like to determine whether or not you can be successful in your strategy, and, if so, how quickly you can execute the cannon rush. Of course, the point of this is to help prepare the correct BM11 for the end of the game.

Input Specification

Line 1: 1 integer, G
For each game:
Line 1: 2 integers, H and W
Next H lines: W characters, representing the ith row of the map, for i = 1 \dots H

Output Specification

For each game:
Line 1: The BM to be typed at the conclusion of the game. Namely, if the probe can reach the cannon rush site, the string "pwned you in X seconds eZ12, learn to play n00b13" (without the quotes and glossary numbers), where X is the minimum number of seconds for it to do so - otherwise, the string terran so broken, apologize for playing this race.

Sample Input

2
4 5
WWEMC
EEEUE
PUWWU
MEEEE
5 4
EWEM
ECUE
EEWE
EWEE
EUPM

Sample Output

pwned you in 8 seconds eZ, learn to play n00b
terran so broken, apologize for playing this race

Explanation of Sample

In the first scenario, the single shortest path that the probe may take to the cannon rush site is illustrated below:

W W E M C
E E E U
W W
M

Note that the first move is made by going "towards" the top-right mineral patch, while the second move is made by going towards the bottom-left one.

In the second scenario, the probe is unable to pass through any of the units, due to the locations of the mineral patches, and as such cannot reach its destination.

Glossary of Terms

1 SC2: StarCraft 2, by Blizzard Entertainment - a game of kings
2 MVP: Most valuable player
3 MVP: A top Korean SC2 team
4 MVP: A top Korean Terran player (who is not on the team MVP)
5 Protoss: The most pleasant race in SC2, which only nice people use
6 Terran: The most despicable race in SC2, which no decent human being would consider
7 Cannon rush: The act of building proxy8 cannons, a common type of cheese9
8 Proxy: A structure made near or in your opponent's base, instead of your own
9 Cheese: A perfectly legitimate strategy which can allow you to win quickly, while leaving your opponent mad
10 Probe: A Protoss unit most useful for its ability to make cannons
11 BM: Customary parting words for your opponent, used to convey your respect for them
12 eZ: Easy
13 n00b: A player whose skill is somewhat lacking in calibre


Comments

There are no comments at the moment.