University of Toronto ACM-ICPC Tryouts 2012

E: MVP

It's down to the final match in the world's biggest SC2¹ tournament! You're the MVP² of MVP³, and you're going up against MVP⁴. There are G (1 ≤ G ≤ 20) games in the series, with a winner decided after all have been played. Being a Protoss⁵ player, you know the perfect way to win against that Terran⁶ scum - with a cannon rush⁷ every single game. Now you just have to execute it perfectly, by quickly getting your probe¹⁰ 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 ≤ H ≤ 1000) rows of W (2 ≤ W ≤ 1000) 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 BM¹¹ for the end of the game.

Input

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..H

Output

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 eZ¹², learn to play n00b¹³" (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:

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

¹ SC2: StarCraft 2, by Blizzard Entertainment - a game of kings
² MVP: Most valuable player
³ MVP: A top Korean SC2 team
⁴ MVP: A top Korean Terran player (who is not on the team MVP)
⁵ Protoss: The most pleasant race in SC2, which only nice people use
⁶ Terran: The most despicable race in SC2, which no decent human being would consider
⁷ Cannon rush: The act of building proxy⁸ cannons, a common type of cheese^9
8 Proxy: A structure made near or in your opponent's base, instead of your own
⁹ Cheese: A perfectly legimate strategy which can allow you to win quickly, while leaving your opponent mad
¹⁰ Probe: A Protoss unit most useful for its ability to make cannons
¹¹ BM: Customary parting words for your opponent, used to convey your respect for them
¹² eZ: Easy
¹³ n00b: A player whose skill is somewhat lacking in calibre

All Submissions
Best Solutions

Point Value: 15
Time Limit: 25.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)