Geek asks and answers

Find an efficient algorithm for matrix operations

This is an interview question:

For a matrix, we define an operation when, when adding 1 to one record, all surrounding records (up, down, left, right) will also be added 1. To obtain a positive matrix, we will find an algorithm for determining whether it is possible to construct a matrix from a zero matrix using such operations.

What is an effective algorithm to solve the issue?

I am currently thinking of using backtracking to try all possible combinations, however this is definitely inefficient. The question seems to be like the game "Lights", but here it is not 0/1, which is complicated.

Thank.

Edit:

For instance:

3 3 can be constructed from 0 0 -> 1 1 -> 2 2 -> 3 3
1 2                         0 0    1 0    1 1    1 2
+5
source share
2 answers

Linear algebra?

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

n 2 . . O(n^6) , .

, , .

+1

( 2x2), - - 3 ( ).
-we

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

, , ,

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
0

More articles:


All Articles