## Mock CCO '18 Contest 3 Problem 3 - Roger Just Plays Some More Chess

View as PDF

Points: 30 (partial)
Time limit: 0.25s
Memory limit: 64M

Problem type

Roger has finally finished running the DMPG and returns to one of his hobbies, playing chess.

Victor has given Roger the following chess-themed math problem: Given an chessboard with good squares, neutral squares, and evil squares, as well as a source and a destination, compute the minimum number of neutral squares that need to be converted to good squares such that there is a path for a knight to take from the source to the destination using only good squares. Along with that, compute how many subsets of that many neutral squares can be converted such that such a path can be constructed.

#### Input Specification

The first line will contain two integers, and .

Each of the next lines contains space-separated integers. These integers will be between and , as follows:

• 0 represents a neutral square
• 1 represents a good square
• 2 represents an evil square
• 3 represents a good square and the source for the knight
• 4 represents a good square and the destination for the knight

#### Output Specification

Output either one or two lines. If it is impossible to construct a path for the knight, output one line containing exactly -1.

Otherwise, output two lines. The first line should be a single integer, the minimum number of squares to convert. The second line should be a single integer, the number of ways to convert that many squares to yield a valid path.

#### Sample Input

4 5
1 0 0 0 0
3 0 0 0 0
0 0 2 0 0
0 0 0 4 0

#### Sample Output

2
3