Mecho

Mecho the bear is on an \(N \times N\) grid of cells: grass G, trees T (impassable), bee hives H, Mecho's start M, and his home cave D. Bees spread from every hive through grass, advancing exactly one cell (in the 4 directions) each minute; bees never enter the cave D, trees, or hives. Mecho walks through grass (and into D) up to \(S\) steps per minute.

Mecho first eats honey at M for a whole number of minutes, during which the bees keep spreading, then walks home. Timing rule: if he eats \(t\) minutes, then after taking \(s\) walking steps the current minute is \(t + \lfloor s / S \rfloor\); he may occupy a cell only if the bees reach it strictly later than that minute.

Output the maximum \(t\) for which Mecho can still reach the cave safely, or -1 if he cannot even by leaving immediately.

Note. This is an adaptation of an IOI function-implementation task to an interactive stdin/stdout problem. The test data is RiseOJ-generated (self-validated against an independent brute force), not the official IOI data.

Interaction / I/O protocol

Input. Line 1: \(N\) and \(S\). The next \(N\) lines each contain a string of \(N\) characters from GTHMD describing the grid.

Output. Print one integer: the maximum eating time, or -1.

Example.

MGGG
GGGG
GGGG
HGGD

with S=1: the answer is the largest number of minutes Mecho may wait and still out-run the bees to D.

• \(1 \le N \le 800\)
• \(1 \le S \le 1000\)
• Exactly one M and one D; at least one H.

Line 1: \(N\) and \(S\). The next \(N\) lines each contain a string of \(N\) characters from GTHMD describing the grid.

Print one integer: the maximum eating time, or -1.

rip 작성

출처 IOI 2009