Znajdź skuteczny algorytm dla operacji macierzowej

Question

To pytanie wywiad:

Dla macierzy definiujemy operację, że gdy dodamy 1 do jednego wejścia, wszystkie okoliczne wpisy (w górę, w dół, left, right) zostanie również dodany przez 1. Biorąc pod uwagę macierz dodatnią, znajdź algorytm określający, czy macierz może zostać zbudowana z matrycy zerowej przy użyciu takiej operacji.

Co to jest skuteczny algorytm do rozwiązania problemu?

Obecnie mogę myśleć o użyciu wstecznego fragmentu, aby wypróbować wszystkie możliwe kombinacje, jednak zdecydowanie nie jest to skuteczne. Pytanie brzmi trochę jak gra Lights Off, ale tutaj nie jest to 0/1, co sprawia, że ​​jest bardziej skomplikowana.

Dzięki.

Edit:

Na przykład:

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

algebry liniowej?

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

n zmienne i równania. Rozwiązać. O(n^6) według metody Gaussa, mogą istnieć inne szybsze metody.

Ponadto matryca jest wyjątkowa, więc może być w stanie ją przyspieszyć.

Answer 2

znalazłem kilka rzeczy (dla matrycy 2x2), chciałbym je najpierw udostępnić
-sum wszystkich elementów w macierzy powinien być podzielny przez 3 (wtedy tylko to jest możliwe).
-Mamy wyrazić danej matrycy w postaci wolno etapów roboczych

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

nie byłoby pewne przypadki, w których nie może być wykonane np

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