SP14980 UOFTBE - MVP

It's down to the final match in the world's biggest SC2 $ ^1 $ tournament! You're the MVP $ ^2 $ of MVP $ ^3 $ , and you're going up against MVP $ ^4 $ . There are $ G $ ( $ 1 \leq G \leq 20 $ ) games in the series, with a winner decided after all have been played. Being a Protoss $ ^5 $ player, you know the perfect way to win against that Terran $ ^6 $ scum - with a cannon rush $ ^7 $ every single game. Now you just have to execute it perfectly, by quickly getting your probe $ ^{10} $ 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 \leq H \leq 1000 $ ) rows of $ W $ ( $ 2 \leq W \leq 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 $ ^{11} $ for the end of the game.

First line: 1 integer, $ G $ For each game: First line: 2 integers, $ H $ and $ W $ Next $ H $ lines: $ W $ characters, representing the $ i $ th row of the map, for $ i = 1..H $

For each game: 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 $ ^{12} $ , learn to play n00b $ ^{13} $ " (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".