1994 ACM Student Programming Contest

Pacific Region

Problem H: Knight's Path

This problem requires you to write a program to find a
minimal path length for chess knight from a given starting
point to a given ending point on an 8x8 chess board with
holes in it.  The knight is allowed to move only onto areas
of the board which do not contain holes.

As shown in the following example, a chess knight depicted
by "O" is allowed to move to any of the positions marked "X"
(assuming position X does not contain a hole):

| |X| |X| |
|X| | | |X|
| | |O| | |
|X| | | |X|
| |X| |X| |

That is, a knight moves in an "L" shape, either 2 squares
horizontally and then one square vertically, or else 2
squares vertically and then one square horizontally.

The input to your program consists of a series of data sets,
where each data set describes one complete board setup.  The
first group of lines in each dataset describes a collection
of rectangles which indicate the area(s) covered by holes on
the board.  Each rectangle is described by a set of 4
integers on a single line. The first two integers give the
row and column respectively of the upper left corner of the
rectangle.  The second two integers give the row and column
respectively of the lower right corner of the rectangle.
Each rectangle in the input is preceded by a line containing
a single POSITIVE integer.  All board squares covered by one
or more rectangles are holes onto which the knight may not
move.

Following the last rectangle in the data set is a single
line containing a NEGATIVE integer. Following that line is a
single line giving the starting point and (desired) ending
point for the knight, in the same format as described above.
This line completes the data set.

As an example, consider a board consisting of two areas
containing holes described as follows:

  1. the rectangle defined by (1,4) as the top left corner
     and (6,8) as the bottom right corner; and

  2. the rectangle similarly defined from (5,1) to (8,2).
  
Further, consider a knight at the starting position (1,1)
which desires to move to the finish position (8,6) on this
board.  This board setup is described by the following
picture where "*" represents a hole, "S" represents the
knight's starting position, "F" represents the knight's
finishing position, and "M" represents a square onto which
the knight moves on the way from S to F:

  1 2 3 4 5 6 7 8
1 S     * * * * *
2       * * * * *
3   M   * * * * *
4       * * * * *
5 * * M * * * * *
6 * *   * * * * *
7 * *  M
8 * *       F

The board shown above would be described by the following
input data set:

1
1 4 6 8
1
5 1 8 2
-1
1 1 8 6

The input to your program is one or more data sets in the
form described above.  For each input data set your program
should output a single line containing a message of the form
                              
                  Minimal Path Length = X,
                              
where X represents the minimum number of moves the knight
can make to arrive at the finish point from the start point.
If there is no legal path from the start point to the finish
point, the program should instead output a message such as
"No Legal Path".