Book of programming problems

Complexity (1-100): 100

Each number in the matrix with dimensions W×H is a value of total biofield emanating from some number of princesses located in the same matrix. Each princess emits biofield in 8 directions (including the cell where the princess is standing): north, north-east, east, south-east, south, south-west, west, and north-west. The biofield level does not depend on the distance. All princesses have biofield level 1, except the genuine one, which has biofield level M. Example:

 2 0 0 2 0
 0 2 0 2 0
 0 0 2 2 2
 2 2 2 2 2
 0 0 2 2 2

M=2, and the genuine princess is in position (3,3), where the first number is the zero-based column index, and the second number is the zero-base row index.

Find the number of spurious princesses and the position of the genuine one. Print the error message if it is not possible. The data is stored in an input file in the following format:


Examples:
1. For the following input file (download): The solution is: Number of spurious princesses: 2, genuine princess at: (1,1).
2. 3×3 matrix. Number of spurious princesses: 3, genuine princess at: (2,1).
3. 10×11 matrix. Number of spurious princesses: 45, genuine princess at: (6,0).
4. 30×31 matrix. Number of spurious princesses: 465, genuine princess at: (10,27).

The biofield level in each position is a sum of all biofields of princesses affecting that position. For example, in the 3×3 matrix the value in position (0,0) is the sum:


where p_ij is 0 if there is no princess in position (i,j), 1 if the princess is spurious and M if this is the genuine princess. We have W×H such linear equations (for each position in the matrix) and the same number of unknowns p_ij. We have to solve the system of linear equations to obtain the answer. We must ensure that the solution meets the following condition:

(*)	all the  pij are either 0 or 1 or M, and there is exactly one  pij=M

In our algorithm, we use a simple Gaussian elimination algorithm to solve the system. There are three possibilities:

1. the equation matrix is not singular, and there is one solution {p_ij}. We check the condition (*) ; if not, the problem does not have a solution;
2. the equation matrix is singular, and the linear equations do not have a solution;
3. the equation matrix is singular, and the linear equations have infinite number of solutions p_ij=x_ij+A_ijFV, where A_ij is a vector of constants and FV is the vector of free variables. In this case, we use a backtracking algorithm to choose values of free variables FV satisfying the condition (*).