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.
