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

View as PDF
Submit solution
Points: 20 (partial)
Time limit: 0.18s
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 R \times C 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.

Constraints

1 \le R, C \le 30

Input Specification

The first line will contain two integers, R and C.

Each of the next R lines will contain C space-separated integers. These integers will be between 0 and 4, 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

Comments


  • 17
    mibster  commented on May 17, 2018, 3:10 p.m.

    why can't the problem name just be "Roger Plays Chess"? why does it have to be "Roger Just Plays Chess"?


  • 14
    mibster  commented on May 3, 2018, 7:15 p.m.

    why can't Roger just play chess? Why does he have to play some chess? WTS. very :angry: