Problem Statement

You are the famous explorer Indiana Jones, or Lara Croft, take your pick. You are exploring the ruins of the dungeons beneath King Lockumup IV the Good's castle in Flatlandia. Of course, the dungeon layout is two-dimensional (like your character), East-West and Up-Down in this case, in a regular grid.

                        Surface
                    | | | | | | | | |
level 0            -R-R-R-R-R-R-R-R-R-
                    | | | | | | | | |
level 1   <- West  -R-R-R-R-R-R-R-R-R- East ->
                    | | | | | | | | |
level 2            -R-R-R-R-R-R-R-R-R-  
                    | | | | | | | | |
                    Depths of Despair

"R" indicates a room. "-" indicates an east-west passageway. "|" indicates an up-down passageway.

Because it is rough going in the passageways between the rooms (there has been no dungeon maintenance for centuries), it is frequently easier to travel through a passageway in a particular direction than in the opposite direction. Each room has four passageways leaving in the directions East (right), West (left), Up, and Down which lead to adjacent rooms (except the Down in the bottom-most rooms, the East in the east-most rooms, and the West in the west-most rooms, which have dead-end passageways due to ancient budget cuts, and Up in the topmost rooms which lead to the surface). The time it takes to travel through a passageway from a given room to the adjacent rooms is given in four String[]s depending on your direction of travel. A digit between 0 and 9 indicates how many time units (in the local system of decimillifortnights, dmfs) are taken to leave the room in that direction and travel through the passageway to the adjacent room. An 'x' character indicates that the travel in that direction is too difficult and can not be done. The dead end passageways (at the edges of the dungeon) have time values, or 'x', specified (because they were in the original plans for the dungeon and we have an old map), but we can not actually travel through these passageways in this problem. The dungeon does *not* wrap in any direction (you are probably thinking of the castle of Queen Mobius the One Sided, the former stripper).

In other words, if you are in room (i,j), where i is the up-down level and j is your easting (ie. how far east you are) coordinate, then

• up[i][j] tells how many dmfs it takes to get to (i-1,j).
• down[i][j] tells how many dmfs it takes to get to (i+1,j).
• east[i][j] tells how many dmfs it takes to get to (i,j+1).
• west[i][j] tells how many dmfs it takes to get to (i,j-1).

If it is obvious to you how these four directional time value arrays map to a directed graph of the dungeon, then skip this next section of the problem description, which goes into detail, and continue reading below for more of the important problem description information.

• For example if given the inputs up and west (shown below)

  up = {"123",      west = {"222",
        "111",              "131",
        "121"}              "444"}
  

  You would have the following time values for each passageway while going up or west.

                     Surface
                      1 2 3 
  level 0            2R2R2R-      Up and West going
                      1 1 1       Passageway times
  level 1      West  1R3R1R- East 
                      1 2 1
  level 2            4R4R4R-      
                      | | |
                Depths of Despair
  

  The dead-end passageways on the far west with times {2, 1, 4} are useless and can be ignored.

  
  
  

  Similarly if you have the inputs down and east (shown below)

  down = {"987",      east = {"222",
          "111",              "3x3",
          "121"}              "111"}
  

  You would have the following time values for each passageway while going down or east.

                     Surface
                      | | |
  level 0            -R2R2R2     Down and East going
                      9 8 7      Passageway times
  level 1      West  -R3RxR3 East 
                      1 1 1
  level 2            -R1R1R1
                      1 2 1 
                 Depths of Despair
  

  The dead-end passageways on the far east with times {2, 3, 1} and the very bottom with times {1, 2, 1} are also useless to you and can be ignored.

We are back from the boring details, here is some more important information.

Unfortunately for you, Dr. Jones or Dr. Croft, you have just triggered an ancient trap, and the dungeon is beginning to to fill with water. First the lowest level fills with water. If the East-West width of the dungeon is n rooms, then each level of the dungeon takes n decimillifortnights to fill. Once full of water, the rooms on that level are no longer accessible. While partly full of water, they are still fully accessible. Time starts at time = 0, at time = n the lowest level becomes inaccessible, at time = 2n the second lowest level becomes inaccessible, etc. So if you are in, or pass through, a room on the lowest level at time >= n, you are dead.

For simplicity, we will only consider if the room is completely filled with water when you enter. So if you leave a nearly filled room, going up through a slow passageway, and arrive somewhat later in a now nearly filled room one level up, this is ok. We will ignore the physics which would lead us to think the passageway would fill with water before the room above it. Only check for drowning when you enter the room. Also the surface (above level 0) never fills with water (we run out of water before then), so you can not drown on the surface.

Your goal is to get to the surface as fast as possible. You start at the location (startLevel, startEasting). "Easting" is how far east you are in the local coordinate system. Rooms have Easting coordinates between 0 and n-1 inclusive, where n is the number of rooms on each level. Return the number of time units (decimillifortnights) it takes to escape, or -1 if escape is impossible.

For example:

up = {"0x4",  down = {"0x9",   east = {"1x9",   west = {"0x9",
      "0x3",          "009",           "0x9",           "0x0",
      "0x3"}          "0x9"}           "009"}           "009"}
startLevel = 2, startEasting = 2

We start in the lower right corner. If water were not an issue, we could reach each of the various rooms with various paths, and the earliest possible times in which we could reach each room are shown below. If we go straight up, the passageways take 3, 3 and 4 dmfs reaching the surface in 10 dmfs. We could also follow the path: up (3 dmfs), west (0 dmfs), down (0 dmfs), west (0 dmfs), up (0 dmfs), up (0 dmfs), and up (0 dmfs) reaching the surface in 3 dmfs. The diagram below shows the minimum time in which we could first get to each room (if water were not an issue), and the passageways used are shown with '|' for up-down, and '-' for east-west.

      3  10      - surface
      |   |  -------------
      3-4 6      - level 0
      |   |
      3 3-3      - level 1
      | | |
      3-3 0      - level 2

But since level 2 fills with water at time 3, we can not move from (1,1) down to (2,1) at time = 3 dmfs. The actual rooms we can reach, considering flooding, are shown below, where 'w' represents a room which is full of water when we first could move into it, and 'x' represents a room we can never reach:

         10      - surface
          |   ------------
      x w-6      - level 0
          |
      x 3-3      - level 1
        | |
      x w 0      - level 2

In this example we can reach the surface in 10 dmfs by going straight up, and this is the minimum, so return 10.

Definition

Constraints

Examples