Boy Jump
InterviewTime limit1sMemory limit512 MB
Given a grid maze and three start cells, find the meeting cell minimizing the maximum shortest-path distance from the three starts, and count all optimal cells or report -1 if unreachable.
- Level
Medium6 of 10
- Topics
- Graph, BFS, Matrix, Implementation
- Solved
- No attempts yet
Problem
"OK, it's going according to plan"
Mami Son, a rising star of Korean hip hop, is running from a group of villains. The group consists of three members: Nucksal, Swings, and Changmo. While fleeing, Mami Son comes across an R*C maze and decides to hide inside it. The villains arrive at the maze late and scatter to search for Mami Son. The villains can always move only up, down, left, or right, they all move at the same speed, and they can move only in cell units. The villains can also stay still in place without moving. Nucksal, Swings, and Changmo start searching for Mami Son from different points, and they are convinced that Mami Son is hiding at the point where the time taken for all three to gather at one point is minimized. Before hiding, Mami Son knows where the villains will start searching, so he tries to hide while avoiding the points the villains will reach.
Mami Son has begun a difficult adventure. Show everyone that the protagonist never dies in this adventure by becoming Mami Son yourself! Given an R*C maze and the starting positions of Nucksal, Swings, and Changmo, tell Mami Son the point where the time taken for the three villains to gather at one point is minimized.
Input
The first line gives the natural numbers R and C, the number of rows and columns of the maze. (2 ≤ R, C ≤ 100) The next R lines give the maze information, each line of length C with no spaces. The digit 0 represents a passable path, and 1 represents a wall. From the next line, three lines give the positions (row, column) of Nucksal, Swings, and Changmo as natural numbers Xi, Yi. (1 ≤ Xi ≤ R, 1 ≤ Yi ≤ C) The villains' positions do not overlap, and they always start on passable paths. The top-left position is (1, 1).
Output
On the first line, output the minimum time taken for the three villains to gather at one point. On the second line, output the number of such points. If no point exists where the three villains can gather, output -1.