j****7
发帖数: 30 | 1 Given two square matrices(initial and final) consisting of elements either
1 or 0. Using minimum number of toggles change the initial to final matrix.
You can toggle either a single row or column at a time. If ith row is
toggled all 1's become 0 and vice versa in that row.
What will be the correct algorithm for this?
For example
|0 0 1|
|1 1 1|
|1 0 1|
to
|1 1 1|
|1 1 0|
|1 0 0| would require
1st row and last column toggle.
Thanks | g*********s
发帖数: 1782 | 2 a* search? eval::=final - trial and always pick up the move closest to
all-0 matrix.
however it also needs some mathematical thinking about the solvability.
either
matrix.
【在 j****7 的大作中提到】
: Given two square matrices(initial and final) consisting of elements either
: 1 or 0. Using minimum number of toggles change the initial to final matrix.
: You can toggle either a single row or column at a time. If ith row is
: toggled all 1's become 0 and vice versa in that row.
: What will be the correct algorithm for this?
: For example
: |0 0 1|
: |1 1 1|
: |1 0 1|
: to
| z***e
发帖数: 5393 | 3 my understanding is it's the same as the "word ladder" problem: giving A and
B and some mutation rules, find out the min mutations from A=>B.
so a straightforward solution is to use BFS to find the shortest path from A
=>B.
Unfortunately, the bfs is a "general" solution, but not the best. wonder if
there is better solution for this particular question.
.
【在 j****7 的大作中提到】
: Given two square matrices(initial and final) consisting of elements either
: 1 or 0. Using minimum number of toggles change the initial to final matrix.
: You can toggle either a single row or column at a time. If ith row is
: toggled all 1's become 0 and vice versa in that row.
: What will be the correct algorithm for this?
: For example
: |0 0 1|
: |1 1 1|
: |1 0 1|
: to
| b***e
发帖数: 1419 | 4 Yes, there is a simple solution here, which is no more than to solve a
set of linear equations.
Taking the example in OP as an example:
1. computer the xor, we get:
1 1 0
0 0 1
0 1 1
2. linearize it, top to bottom, left to right, let R be:
1 1 0 0 0 1 0 1 1
3. List all the transformations you can do, let T be:
1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1
1 0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1
4. Let T' be the transit of T, and R' be the transit of R (so R's is a
column). Now the problem becomes as simple as to find solution for:
T' * X = R'
where multiplication and addition are all modulo 2.
The key is to note that, you will only need to flip a row/col at most
once,
and the order in which you flip it doesn't matter. |
|
