Well, here is my slightly different attempt.
Idea
Note. I assume that “We cannot change the first line” means “We cannot change the very top line”.
Some terminology:
- With bit switching, I mean changing its value from 0 to 1 or from 1 to 0.
- By flipping a bit, I mean switching the bit and 4 bits around it.
The act of switching bits is commutative. That is, it does not matter in which order we switch it - the final result will always be the same (this is a trivial statement). This means that flipping is also a commutative action, and we can flip the bits in any order we like.
The only way to switch the value at the edge of the matrix is to flip the bit next to it in an uneven number of times. Since we are looking for the lowest flips, we want to flip it a maximum of 1 time. So, in a scenario like the one below, x will need to be flipped exactly once, and y will need to be flipped exactly 0 times.
. . 1 x 0 y . ,
Two conclusions can be drawn from this:
The angle of the matrix can never be switched - if 1 is found on the corner, it is impossible to make the matrix zero with any number of turns. Thus, your first example can be discarded without even flipping one bit.
the bit next to the corner should have the same meaning as the bit on the other side. This matrix , which you posted in a comment, can thus also be discarded without dragging one bit (lower right corner).
Two examples of the above conditions:
0 1 . 0 x . . . .
It is impossible, since x needs to be flipped exactly once and exactly zero time.
0 1 . 1 x . . . .
Perhaps x needs to be flipped exactly once.
Algorithm
Now we can make a recursive argument, and I propose the following:
- We are given a matrix
m by n . - Check the conditions of the angle above as indicated above (i.e. corner! = 1, the bit next to the angle should be the same value). If both criteria are violated, return
impossible . - Scroll to the edge of the matrix. If 1 occurs, flip the nearest bit inside and add 1 to the counter.
- Now reload from # 1 using the matrix
m - 2 by n - 2 (top and bot rows are deleted, left and right columns) if any dimension is> 2, otherwise print the counter and close.
Implementation
Initially, I thought it would turn out beautifully and beautifully, but as they say, it is a little more cumbersome than I initially thought it would be the way we should track a lot of indexes. Ask questions if you are wondering about implementation, but in essence it is a pure translation of the steps described above.
#include <iostream> #include <vector> using Matrix = std::vector<std::vector<int>>; void flip_bit(Matrix& mat, int i, int j, int& counter) { mat[i][j] = !mat[i][j]; mat[i - 1][j] = !mat[i - 1][j]; mat[i + 1][j] = !mat[i + 1][j]; mat[i][j - 1] = !mat[i][j - 1]; mat[i][j + 1] = !mat[i][j + 1]; ++counter; } int flip(Matrix& mat, int n, int m, int p = 0, int counter = 0) { // I use p for 'padding', ie 0 means the full array, 1 means the outmost edge taken away, 2 the 2 most outmost edges, etc. // max indices of the sub-array int np = n - p - 1; int mp = m - p - 1; // Checking corners if (mat[p][p] || mat[np][p] || mat[p][mp] || mat[np][mp] || // condition #1 (mat[p + 1][p] != mat[p][p + 1]) || (mat[np - 1][p] != mat[np][p + 1]) || // condition #2 (mat[p + 1][mp] != mat[p][mp - 1]) || (mat[np - 1][mp] != mat[np][mp - 1])) return -1; // We walk over all edge values that are *not* corners and // flipping the bit that are *inside* the current bit if it 1 for (int j = p + 1; j < mp; ++j) { if (mat[p][j]) flip_bit(mat, p + 1, j, counter); if (mat[np][j]) flip_bit(mat, np - 1, j, counter); } for (int i = p + 1; i < np; ++i) { if (mat[i][p]) flip_bit(mat, i, p + 1, counter); if (mat[i][mp]) flip_bit(mat, i, mp - 1, counter); } // Finished or flip the next sub-array? if (np == 1 || mp == 1) return counter; else return flip(mat, n, m, p + 1, counter); } int main() { int n, m; std::cin >> n >> m; Matrix mat(n, std::vector<int>(m, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { std::cin >> mat[i][j]; } } int counter = flip(mat, n, m); if (counter < 0) std::cout << "impossible" << std::endl; else std::cout << counter << std::endl; }
Exit
3 3 1 0 1 1 1 1 0 1 0
impossible
3 3 0 1 0 1 1 1 0 1 0
one
6 8 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0
10
4 6 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0
impossible