Speedwalk

PROBLEM STATEMENT

A MUD is a multiplayer text game, wherein the game world is divided into rooms.
Each room may have exits in six cardinal directions: north, east, south, west,
up, and down.  Each exit, if it exists, goes to another room on the MUD.  On a
particular MUD you are developing for, the rooms are numbered in the server's
database, and a list enumerates the exits from each room.  This MUD allows
players to navigate between rooms by simply typing the name of the direction
they wish to travel in.  It also supports the use of "speedwalks", which are
strings of movements condensed on to a single line, with optional counts before
each direction.  For example, the speedwalk "2s3w4nes2d" will cause a player to
move south twice, west three times, north four times, east, south, and down
twice, in that order.
 
You are adding a new command that generates a simplified speedwalk from your
current location to another room on the MUD.  In a simplified speedwalk, any
repeating series of the same movement should be condensed to a number of
occurrences followed by that movement. For instance, nnnee could be simplified
to 3n2e.  In the case that multiple speedwalks would solve this problem, you
should select the shortest one, in terms of characters.  If two paths tie on
printed length, return the one that represents the fewest room-to-room
transitions; if there is still a tie, choose the speedwalk which comes first
lexicographically (i.e., as ordered by strcmp() in C or String.compareTo() in
Java, using the ASCII collating sequence).  If the target room is not reachable
from your current location, return "***".

DEFINITION

Class Name: Speedwalk
Method Name: shortest
Parameters: int, int, String[]
Returns: String

Here is the method signature (make sure your method is public): String
shortest(int start, int target, String[] rooms);

Each element of rooms is a string of the form

  "<num>: <north> <east> <south> <west> <up> <down>"

listing the exits from the room with number <num>.  When no exit exists in a
direction, 0 (zero) should be inserted in that position. 

TopCoder will ensure the following:
* all references to rooms will be in the range 1 to 99, inclusive.  
* the start and target rooms will be defined in rooms, as well as any rooms
referenced as exits.
* no room will be defined more than once.
* rooms will be formatted exactly as shown above: a single colon following the
room number described by that string, and exactly one space between items.

EXAMPLES
Given a starting room of 5, a target of 13, and the following room list:
{ "3: 3 3 3 3 9 5",  
  "4: 0 0 0 0 5 0",  
  "5: 68 5 66 5 3 4",              
  "8: 0 12 9 37 0 0",
  "9: 8 0 0 0 0 3",                
  "12: 0 13 0 0 0 0",
  "13: 0 0 0 4 0 0",
  "37: 0 0 8 0 0 12",
  "66: 5 0 0 0 0 0",
  "68: 0 0 5 0 0 0" }              
The return value should be "2un2e", corresponding to the sequence of rooms 5 ->
3 -> 9 -> 8 -> 12 -> 13.

Given a starting room of 5, a target of 7, and the following room list:
{ "5: 0 0 7 0 0 0",
  "7: 0 0 0 0 0 0" }
The best speedwalk (indeed, the *only* speedwalk) is "s".             

Given a starting room of 7, a target of 5, and the previous list of rooms,
there is no path available, so your method should return "***".        

Given a starting room of 1, a target of 4, and the following room list:
{ "1: 2 3 0 0 0 0", 
  "2: 3 4 0 0 0 0",
  "3: 4 0 0 0 0 0",
  "4: 1 2 1 0 0 0" } 
We can have "3n", or "en", or "ne".  Since they all tie on printed length, we
consider those which take the fewest steps, and choose "en", as it would appear
first in a sorted list. 

Given a starting room of 55, a target of 99, and the following room list:
{ "99: 0 10 0 0 0 0",
  "5: 0 99 0 4 0 0",
  "4: 0 5 0 3 0 0",  
  "3: 0 4 0 2 0 0", 
  "2: 0 3 10 55 0 0", 
  "55: 0 2 0 0 0 0",
  "10: 2 99 0 0 0 0" }
The return value should be "5e".  Even though "ese" would also work, and is
fewer steps, its string representation is longer.