TopCoder problem "IncompatibleMice" used in TCO08 Semifinal 3 (Division I Level Two)



Problem Statement

    

You have trained 3 mice to solve a maze. They know the maze well, and are capable of running from any point to any other point in the maze following the shortest path possible, provided that a path exists between those two points. If at any point a mouse can go in multiple directions that will all result in the same shortest distance to its end point, it will choose among them with equal probability.

The maze is defined on a 2D grid of squares, where each square is either an open space or a wall. It will be given as a String[] maze, and will contain exactly 1 of each of the following 6 characters: 'a', 'A', 'b', 'B', 'c', and 'C'. These characters represent open spaces, and also define the starting and ending points for each mouse. Mouse A runs from 'a' to 'A', mouse B runs from 'b' to 'B', and mouse C runs from 'c' to 'C'. Each of the other characters in maze will be either '#' (a wall) or '.' (an open space). Mice may not run off the sides of the maze.

The mice do not like each other. In fact, if in the course of running the maze, two mice ever meet, they will fight to the death. It takes a mouse 1 second to run from the center of one open space to the center of a horizontally or vertically adjacent open space. Two mice "meet" if they ever attempt to occupy the center of the same open space at the same time, or if they move in opposite directions between the same two adjacent open spaces at the same time.

You do not want this to happen. You want all three mice to run a different path through the same maze, and you may start the mice any integer number of seconds apart (including 0 seconds), in any order. The mice do not enter the maze until you start them, and you remove a mouse from the maze immediately after it reaches its destination square. You must preselect the starting times for all three mice before the first mouse begins. That is, you cannot wait to see which path one mouse follows before deciding when to start another. Return the smallest possible total time in seconds (from the time the first mouse starts its path to the time the last mouse finishes) such that there is no chance of any mice meeting in the maze. If it is impossible for all 3 mice to reach their destination, return -1.

 

Definition

    
Class:IncompatibleMice
Method:totalTime
Parameters:String[]
Returns:int
Method signature:int totalTime(String[] maze)
(be sure your method is public)
    
 

Constraints

-maze will contain between 1 and 50 elements, inclusive.
-Each element of maze will contain between 1 and 50 characters, inclusive.
-All elements of maze will have the same length.
-maze will be fomatted as described in the problem statement.
 

Examples

0)
    
{ "########",
  "###a####",
  "##...###",
  "#b...B##",
  "##...###",
  "###A#cC#",
  "########" }


Returns: 5
The lengths of the 3 paths are 4, 4, and 1. If you start mice A and B at the same time, they will meet where their paths cross. However if you delay one of them by 1 second, they will miss each other. Mouse C is not a factor and can be started anytime between 0 and 4 seconds after the first mouse.
1)
    
{ "A##.##B",
  ".......",
  "b#####a",
  "#.c.C.#" }
Returns: 15
Here, an optimal solution is to start mouse B 7 seconds after mouse A. After 7 seconds, mouse A will be between the 'A' and 'b' characters. Mouse B starts at this time one square below. One second later (after a total of 8 seconds), mouse A has moved on to its destination square, and mouse B has moved between the 'A' and the 'b'. It will then take 7 more seconds for mouse B to complete its path. Again, mouse C is not a factor.
2)
    
{ "##.#...#.##",
  "##...#...##",
  "a..#...#..A",
  "##...#...##",
  "b..#...#..B",
  "##...#...##",
  "c..#...#..C",
  "##...#...##",
  "##.#...#.##" }
Returns: 16
Each mouse has 6 possible paths to its destination, all of length 14. All mice could potentially pass through the center square of the maze in the middle of their path. Therefore, they must all start at different times. If you start one mouse 1 second after another, and the third mouse 1 second after that, they will finish in a total of 16 seconds without any possibility of conflict.
3)
    
{ "....b....",
  ".........",
  "..a......",
  ".........",
  "c.......C",
  ".........",
  "......A..",
  ".........",
  "....B...." }
Returns: 10
4)
    
{ "aB........Ab.cC" }
Returns: 20
Mice A and B each have a path of length 10, but you cannot start one until the other has completely finished.
5)
    
{ "...a...",
  ".#####.",
  "Bc...bC",
  "###.###",
  "###A###" }
Returns: 13
Unfortunately, we must select the starting times of mice before the experiment, so we will not be able to let the first mouse A run and see which way will it choose.
6)
    
{ ".a.A.#...",
  ".b...#.B.",
  ".c.C.#..." }
Returns: -1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8767

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12017&pm=8767

Writer:

legakis

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Search