| Problem ID | knight |
|---|---|
| Difficulty level (0..10) | 4 |
| Maximum runtime | 1 minute |
| Original problem | |
| Seen at |
In a checkboard 8x8 there is one knight (the known chess piece) and several holes (invalid areas). Given the start and desired end position of the knight, as also as the coordinates of the invalid areas, give the minimum number of steps for the knight to reach its destination. If no path exists or start or end position are invalid, issue the appropriate message.
Input: One line with a non-negative integer N.
N lines containing 4 integers each, marking,as 2 pairs, the oposite squares of
an orthogonal invalid area.
Then one line with the start and end coordinates
of the knight.
All coordinates numbers are from 1 to 8. No line will be longer than 100 characters. Numbers are separated by whitespace (spaces and/or tabs).
Output: "The number of "Minimal Path Length = X" without the quotes and X the least steps no. If no path exists, "No Legal Path" (without the quotes.
Sample input:
1
6 6 7 7
1 1 3 1
Sample output:
Minimal Path Length = 2