**Challenge 6** - Knight Labyrinth

The princess is in trouble again. This time she's trapped in a labyrinth. Your duty as her loyal knight is to rescue her. She looks so close… just one square away!

The brave knight moves through the map in L-shaped jumps like a chess knight (it can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally). The knight can jump over any square but he cannot land on an invalid square.

The map has the following squares (each square is represented by one character):

- '
**K**': current location of the knight - '
**P**': princess location - '
**#**': invalid square - '
**.**': valid square

The commands to move the knight (located in square K) are:

2U1L |
2U1R |
|||

1U2L |
1U2R |
|||

K |
||||

1D2L |
1D2R |
|||

2D1L |
2D1R |

For example, **2U1R** command will move the knight 2 square up and 1 square right.
For convenience commands in lowercase and in reverse order are also valid.
So in this case **1r2u** represents the same command

Quick! Help the knight! You can access the labyrinth here:

**contest-daemons.tuenti.net:2003**

### Limits

Height and width of the map are less than 110 squares

### Input

None

### Output

Find the princess (jump with the knight to the princess square), and she'll tell you the secret key. There is only one key and it's valid for both phases, testing and submission.

### Problem stats

Completion time: |
min: 0:34:40 h10th percentile: 2:26:48 h90th percentile: 45:51:02 hmax: 122:38:32 h |
---|---|

Test phase time: |
10th percentile: 2:26:36 h90th percentile: 45:39:34 h |

Submit phase time: |
10th percentile: 0:00:10 h90th percentile: 0:14:43 h |

# of completions: | 185 |