PROBLEM STATEMENT
A psychologist wants to study instinctive route-making behavior in lab rats.
She builds a two-dimensional enclosure and places blocks (each one foot wide
and one foot deep) at random points inside the enclosure. She then places a
piece of cheese at a random point in the enclosure and a lab rat at another
random point. Here is an example setup, where a square foot of space is
represented by a period, a block is represented by an X, the rat is represented
by an R, and the piece of cheese is represented by a C (spaces are added for
easy reading):
. R . . .
. . X . .
. . . . X
X . X . X
. . . C .
Before putting the rat in the enclosure, the psychologist shows the location of
the piece of cheese to the rat. Naturally, the rat will attempt to take a path
with the shortest possible distance to the cheese. But the rat isn't that
intelligent so the rat will only move towards the cheese and never move away
from the cheese. Assume that the rat can only move horizontally or vertically,
one point at a time. In the above example, there are 3 possible routes the rat
can take to get to the cheese:
1) East 2 points, South 4 points
2) South 2 points, East 2 points, South 2 points
3) South 4 points, East 2 points
Create a class RatRoute that contains the method numRoutes, which takes a
String[] representing the configuration of the test (each String represents one
row of the maze), and returns an int representing the number of possible routes
the rat can take to get to the cheese without ever increasing the distance
between itself and the cheese at any point on its path (see first NOTE).
DEFINITION
Class: RatRoute
Method: numRoutes
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int numRoutes(String[] enc);
NOTES
- The distance between the rat and the cheese is the Euclidean distance. For
example if the cheese is 4 points North of the rat and 3 points East of the
rat, the distance between the rat and the cheese is 5.
- The rat cannot pass through, over or under the blocks that are in place.
- It is possible to have a configuration in which the rat can not reach the
cheese by moving only towards it(horizontally or vertically) but could reach
the cheese if it were to move away from the cheese. In such cases, return 0.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- There are between 1 and 10 rows in the enclosure, inclusive.
- There are between 1 and 10 columns in the enclosure, inclusive.
- The enclosure is perfectly rectangular. That is, each element of String[] enc
will be of the same length.
- There are between 0 and (rows*columns-2) blocks in the enclosure, inclusive.
- There is exactly one rat.
- There is exactly one piece of cheese.
- Each character in each element of String[] enc can only be one of the
following: a period (representing a space), an X (representing a block), an R
(representing the rat), or a C (representing the cheese).
EXAMPLES
=========
Example 1
=========
enc = {
".R...",
"..X..",
"....X",
"X.X.X",
"...C."}
For explanation, see above.
The method returns 3.
=========
Example 2
=========
enc = {
"...X.C",
"R....."}
There are 2 possible routes:
1) East 5 points, North 1 point
2) East 4 points, North 1 point, East 1 point
The method returns 2.
=========
Example 3
=========
enc = {
"C..X.",
".....",
"X..R.",
"....."}
There are 8 possible routes:
1) North 1 point, West 1 point, North 1 point, West 2 points
2) North 1 point, West 2 points, North 1 point, West 1 point
3) North 1 point, West 3 points, North 1 point
4) West 1 point, North 2 points, West 2 points
5) West 1 point, North 1 point, West 1 point, North 1 point, West 1 point
6) West 1 point, North 1 point, West 2 points, North 1 point
7) West 2 points, North 2 points, West 1 point
8) West 2 points, North 1 point, West 1 point, North 1 point
The method returns 8.
=========
Example 4
=========
enc = {
"C........R",
".........."}
The method returns 1.
=========
Example 5
=========
enc = {
"C",
".",
".",
".",
".",
".",
".",
"X",
".",
"R"}
The method returns 0.
=========
Example 6
=========
enc = {
"....X",
".CXX.",
".XX..",
"....R"}
The only way the rat can get to the cheese is to go West 4 points, North 2
points, and East 1 point.
However, when the rat moves into the lower-left corner, it increases the
distance between itself and the cheese, so this route does not count.
The method returns 0.