PROBLEM STATEMENT
A group of cats and mice have been placed on a floating 2-dimensional
floorboard. Initially, each tile of the floorboard is occupied by one of four
possible things: a cat, a mouse, a wall, or empty space. A timer ticks once
every second - the cats and mice each make a move simultaneously when the timer
ticks. (The initial floorboard represents the floorboard at 0 seconds - the
timer makes its first tick at 1 second). Cats and mice can only perform two
physical movements: they can turn, or they can walk to an adjacent tile. They
cannot turn and walk in the same move. Each move is instantaneous and takes no
time to perform.
Cats obey the following rules:
-If there is no wall in front of the cat, it will move forward one tile
(multiple cats can coexist on a single tile).
-Otherwise, it will turn to its right.
Mice obey the following rules:
-If there is no wall behind the mouse, it will move backward one tile (multiple
mice can coexist on a single tile).
-Otherwise, it will turn to its left.
Cats and mice are not too smart (as evidenced by the rules they follow), so
they may fall off the floorboard entirely. In that case, they will disappear
(and no longer exist on the floorboard). Also, mice will disappear instantly
if they end up in the same tile as a cat. However, if a mouse and cat cross
paths without landing in the same tile, the mouse will not disappear (at least
not because of that particular cat).
The initial floorboard is given as a String[] (this String[] will be referred
to as initialBoard for the rest of the problem statement). Each String in
initialBoard represents a single row of the floorboard (first String is the top
row, last String is the bottom row). Each String will contain ints
representing the contents of that row:
0 = empty space
1 = wall
2 = cat
3 = mouse
So, on a m x n floorboard, coordinates (0,0) will be represented by the first
int in the first String in initialBoard. Coordinates (m-1,n-1) will be
represented by the last int in the last String in initialBoard. Coordinates
(x,y) will be represented by the xth character of the yth String in
initialBoard - where x represents the column and y represents the row.
Initially, all mice will face in the direction specified by the
initialMouseDirection parameter. This value is an integer:
0 = north
1 = east
2 = south
3 = west
All cats will initially face the opposite direction as the mice (for example,
if the mice are facing north initially, the cats will be facing south).
Implement a class CatAndMouse, which contains a method numLivingMice.
numLivingMice returns the number of living mice on the floorboard after a
specified number of seconds have elapsed.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
*initialBoard can contain between 0 and 20 elements inclusive. Strings in
initialBoard can be between 0 and 20 characters in length, and each String will
be of equal length.
*characters in the elements of initialBoard will be integers between 0 and 3
inclusive.
*timeElapsed will be between 0 and 100 inclusive.
*initialMouseDirection will be between 0 and 3 inclusive.
DEFINITION
Class name: CatAndMouse
Method name: numLivingMice
Parameters: String[], int, int
Returns: int
The method signature is:
int numLivingMice(String[] initialBoard, int timeElapsed, int
initialMouseDirection);
Be sure your method is public.
EXAMPLES
initial floorboard:
{"1011",
"3333",
"2110",
"1112"}
timeElapsed: 2
initialMouseDirection: 2 (south)
(Refer to http://www.topcoder.com/contest/CatAndMouse1.html for a visual
representation of this example.)
There are four mice (all facing south, and all in the second row from the top)
on the floorboard initially. There are two cats (both facing north).
After one second:
{"1311",
"2033",
"0112",
"1110"}
One mouse has been eaten by a cat (which has moved forward one cell) because it
could not move backwards. Another mouse has moved backwards (north) one cell.
The other two mice cannot move backwards, so they re-orient themselves to face
to their left. The other cat has moved forward one cell.
After two seconds:
{"1011",
"2332",
"0110",
"1110"}
One mouse has fallen off the northern border of the floor and disappeared. The
other two mice have moved backwards one cell each. One cat cannot move
forward, so it turns to its right. The other cat moves forward one cell.
Return value: 2 living mice on the board
Another example:
initialBoard:
{"111",
"121",
"101",
"101",
"131"}
timeElapsed: 3
initialMouseDirection: 2 (south)
(Refer to http://www.topcoder.com/contest/CatAndMouse2.html for a visual
representation of this example.)
After one second:
{"111",
"121",
"101",
"131",
"101"}
The cat (which was facing north) cannot move forward, so it turns right.
The mouse goes backward one cell.
After two seconds:
{"111",
"121",
"131",
"101",
"101"}
The cat (which was facing east) cannot move forward this time either, so
it turns right again. The mouse goes backward another cell.
After three seconds:
{"111",
"131",
"121",
"101",
"101"}
The cat moves forward one cell. The mouse goes backward one cell. They
cross paths, but land in different cells, so the mouse survives.
Return value: 1 living mouse on the board
More examples:
----
initialBoard:
{"13131",
"21212",
"01010",
"31113",
"21012"}
timeElapsed: 1
initialMouseDirection: 0
Return value: 4
----
initialBoard (same as above):
{"13131",
"21212",
"01010",
"31113",
"21012"}
timeElapsed: 2
initialMouseDirection: 0
Return value: 2
----
initialBoard:
{"1111",
"1331",
"1331",
"1111"}
timeElapsed: 4
initialMouseDirection: 1
return value: 4