# Tuenti Challenge 10

## 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

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.

## Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want. Be careful with extra whitespace. The output should be exactly as described.

### Test your program against the input provided in the test phase

Download test input

Program output:

### Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you have to solve the test phase before you can submit your code. You must provide the source code used to solve the challenge and you can only make one submission. After your solution is submitted, you won't be able to modify it to fix issues or make it faster.

If you have any doubts, please see the info section.

### Problem stats

Completion time: min: 0:34:40 h 10th percentile: 2:26:48 h 90th percentile: 45:51:02 h max: 122:38:32 h 10th percentile: 2:26:36 h 90th percentile: 45:39:34 h 10th percentile: 0:00:10 h 90th percentile: 0:14:43 h 185