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
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.
Line 1: 1 integer, ~G~
For each game:
Line 1: 2 integers, ~H~ and ~W~
Next ~H~ lines: ~W~ characters, representing the ~i~th row of the map, for ~i = 1 \dots H~
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.
2 4 5 WWEMC EEEUE PUWWU MEEEE 5 4 EWEM ECUE EEWE EWEE EUPM
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:
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
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