## This problem is taken from a recent ACM South-Pacific Programming Contest and will test your understanding of dynamic programming.

### computer science

##### Description

Computer Science

Assignment 2

Knight’s Shortest Path                                                                                              Marks: 5

This problem is taken from a recent ACM South-Pacific Programming Contest and will test your understanding of dynamic programming.

Master Li likes to play various types of chess and was thinking about how efficient the knight piece moves between positions on a chess board. It is known that the knight travels (in one move) two cells in one direction then one cell in the other axis as shown in the international 8 8 chessboard shown below on the left. There are also various flavours of chess, including the Chinese version (xiangqi) shown on the right, where the knight is placed on the intersections of lines (equivalent to a 10 9 cell-based board).

With various sizes of boards, Master Li wants to know the minimum number of knight moves to travel from opposite corners of a board (e.g. go from cell 1a to cell 8h). In addition, if there is more than one possible path he wants to know the total number of different minimum paths. Can you help him calculate this information?

Input

The input consists of a series of up to 100 test cases. Each test case is a line consisting of two integers  , denoting the number of cells in vertical direction (rows) and horizontal direction (columns) for the chessboard, respectively. The input is terminated by a test case that does not have a valid knight path that reaches the opposite corner and no reported results is required for this case.

Output

For each test case with a valid knight path, output a single line showing the smallest number of knight moves and a count of the number of distinct paths of that shortest distance between two opposite corners.

Sample input and output

 Input Output 1 1 0 1 4 4 2 2 4 5 3 1 2 4

Submission

For this assignment name your source code knightE.ext and knightH.ext where ext denotes one of the programming language (python or other) extensions supported by the automarker. Please use just one source file per problem. Here the suffix E denotes ‘E’asy (test data) and H denotes ‘H’arder (test data). Three marks are allocated to knightE.ext and two marks are allocated for knightH.ext.

## Related Questions in computer science category

##### Disclaimer
The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.