Encontrar un algoritmo eficiente para una operación de matriz

Question

Ésta es una pregunta de la entrevista:

Para una matriz, se define una operación que cuando añadimos 1 a una entrada, todas las entradas de los alrededores (arriba, abajo, izquierda, derecha) también será agregado por 1. Dada una matriz positiva, encuentre un algoritmo para determinar si la matriz puede construirse a partir de una matriz cero usando tal operación.

¿Qué es un algoritmo eficiente para resolver la pregunta?

En lo que actualmente puedo pensar es en utilizar la función de retroceso para probar todas las combinaciones posibles, sin embargo, esto definitivamente no es eficiente. La pregunta es similar al juego Lights Off, pero aquí no es 0/1, lo que lo hace más complicado.

Gracias.

Editar:

Por ejemplo:

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3 
1 2       0 0 1 0 1 1 1 2 

Answer 1

álgebra lineal?

Cell i,j is touched x<sub>ij</sub> times. 

n variables y ecuaciones. Resolver. O(n^6) por el método gaussiano, pueden existir otros métodos más rápidos.

Además, la matriz es especial, por lo que es posible que sea más rápida.

Answer 2

encontré algunas cosas (para la matriz 2x2), me gustaría compartirlas primero
-sum de todos los elementos en la matriz debería ser divisible por 3 (entonces solo es posible).
-tenemos para expresar una matriz dada en permitido forma operación pasos

3 3 -> 2* 1 1 + 1* 1 1 
1 2  0 1   1 0 

habría algunos casos en los que esto no se puede hacer, por ejemplo,

5 3 ->2* 1 0 + 2* 1 1  = 4 2 
2 4  1 1   0 1  2 4 

5 3 - 4 2  = 1 1 (this is not allowed operation) 
2 4  2 4  0 0