Fill 2-dimensional array with zeros by flipping groups of cells

Question

There is a problem where I need to fill an array with zeros, with the following assumptions:

• in the array there can only be 0 and 1
• we can only change 0 to 1 and 1 to 0
• when we meet 1 in array, we have to change it to 0, such that its neighbours are also changed, for instance, for the array like the one below:

1 0 1
1 1 1
0 1 0

When we change element at (1,1), we then got the array like this:

1 1 1
0 0 0
0 0 0

• We can't change the first row
• We can only change the elements that are in the array
• The final result is the number of times we have to change 1 to 0 to zero out the array

1) First example, array is like this one below:

0 1 0
1 1 1
0 1 0

the answer is 1.

2) Second example, array is like this one below:

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

The answer is 10.

There also can be situations that its impossible to zero out the array, then the answer should be "impossible".

Somehow I can't get this working: for the first example, I got the right answer (1) but for the second example, program says impossible instead of 10.

Any ideas what's wrong in my code?

#include <iostream>
using namespace std;

int main(int argc, char **argv)
{
    int n,m;

    cin >> n >> m;

    bool tab[n][m];

    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin >> tab[i][j];

    int counter = 0;

    for(int i=0; i<n-1; i++)
    {
        for(int j=0; j<m-1; j++)
        {
            if(tab[i][j] == 1 && i > 0 && j > 0)
            {
                tab[i-1][j] = !tab[i-1][j];

                tab[i+1][j] = !tab[i+1][j];

                tab[i][j+1] = !tab[i][j+1];

                tab[i][j-1] = !tab[i][j-1];

                tab[i][j] = !tab[i][j];

                counter ++;
            }
        }
    }

    bool impossible = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(tab[i][j] == 1)
            {
                cout << "impossible\n";
                impossible = 1;
                break;
            }
        }
        if(impossible)
            break;
    }

    if(!impossible)
        cout << counter << "\n";

    return 0;
}

Answer 1

I believe that the reason your program was returning impossible in the 6x8 matrix is because you have been traversing in a left to right / top to bottom fashion, replacing every instance of 1 you encountered with 0. Although this might have seemed as the right solution, all it did was scatter the 1s and 0s around the matrix by modifying it's neighboring values. I think that the way to approach this problem is to start from bottom to top/ right to left and push the 1s towards the first row. In a way cornering (trapping) them until they can get eliminated.

Anyway, here's my solution to this problem. I'm not entirely sure if this is what you were going after, but I think it does the job for the three matrices you provided. The code is not very sophisticated and it would be nice to test it with some harder problems to see if it truly works.

#include <iostream>

static unsigned counter = 0;

template<std::size_t M, std::size_t N>
void print( const bool (&mat) [M][N] )
{
    for (std::size_t i = 0; i < M; ++i)
    {
        for (std::size_t j = 0; j < N; ++j)
            std::cout<< mat[i][j] << " ";
        std::cout<<std::endl;
    }
    std::cout<<std::endl;
}

template<std::size_t M, std::size_t N>
void flipNeighbours( bool (&mat) [M][N], unsigned i, unsigned j )
{
    mat[i][j-1] = !(mat[i][j-1]);
    mat[i][j+1] = !(mat[i][j+1]); 
    mat[i-1][j] = !(mat[i-1][j]); 
    mat[i+1][j] = !(mat[i+1][j]); 
    mat[i][j]   = !(mat[i][j]);
    ++counter;
}

template<std::size_t M, std::size_t N>
bool checkCornersForOnes( const bool (&mat) [M][N] )
{
    return (mat[0][0] || mat[0][N-1] || mat[M-1][0] || mat[M-1][N-1]);
}

template<std::size_t M, std::size_t N>
bool isBottomTrue( bool (&mat) [M][N], unsigned i, unsigned j )
{
    return (mat[i+1][j]);
}

template<std::size_t M, std::size_t N>
bool traverse( bool (&mat) [M][N] )
{
    if (checkCornersForOnes(mat))
    {
        std::cout<< "-Found 1s in the matrix corners." <<std::endl;
        return false;
    }

    for (std::size_t i = M-2; i > 0; --i)
        for (std::size_t j = N-2; j > 0; --j)
            if (isBottomTrue(mat,i,j))
                flipNeighbours(mat,i,j);

    std::size_t count_after_traversing = 0;
    for (std::size_t i = 0; i < M; ++i)
        for (std::size_t j = 0; j < N; ++j)
            count_after_traversing += mat[i][j];

    if (count_after_traversing > 0)
    {
        std::cout<< "-Found <"<<count_after_traversing<< "> 1s in the matrix." <<std::endl;
        return false;
    }
    return true;
}


#define MATRIX matrix4

int main()
{

    bool matrix1[3][3] = {{1,0,1},
                         {1,1,1},
                         {0,1,0}};

    bool matrix2[3][3] = {{0,1,0},
                         {1,1,1},
                         {0,1,0}};

    bool matrix3[5][4] = {{0,1,0,0},
                         {1,0,1,0},
                         {1,1,0,1},
                         {1,1,1,0},
                         {0,1,1,0}};

    bool matrix4[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}};


    std::cout<< "-Problem-" <<std::endl;
    print(MATRIX);

    if (traverse( MATRIX ) )
    {
        std::cout<< "-Answer-"<<std::endl;
        print(MATRIX);
        std::cout<< "Num of flips = "<<counter <<std::endl;
    }
    else
    {
        std::cout<< "-The Solution is impossible-"<<std::endl;
        print(MATRIX);
    }
}

Output for matrix1:

-Problem-
1 0 1 
1 1 1 
0 1 0 

-Found 1s in the matrix corners.
-The Solution is impossible-
1 0 1 
1 1 1 
0 1 0 

Output for matrix2:

-Problem-
0 1 0 
1 1 1 
0 1 0 

-Answer-
0 0 0 
0 0 0 
0 0 0 

Num of flips = 1

Output for matrix3:

-Problem-
0 1 0 0 
1 0 1 0 
1 1 0 1 
1 1 1 0 
0 1 1 0 

-Found <6> 1s in the matrix.
-The Solution is impossible-
0 1 1 0 
1 0 1 1 
0 0 0 0 
0 0 0 1 
0 0 0 0 

Output for matrix4 (which addresses your original question):

-Problem-
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 

-Answer-
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

Num of flips = 10

Answer 2

Ok, here comes my somewhat different attempt.

Idea

Note: I assume here that "We can't change the first row" means "We can't change the outmost row".

Some terminology:

• With toggling a bit I mean changing it's value from 0 to 1 or 1 to 0.
• With flipping a bit I mean toggling said bit and the 4 bits around it.

The act of toggling a bit is commutative. That is, it does not matter in what order we toggle it—the end result will always be the same (this is a trivial statement). This means that flipping is also a commutative action, and we are free to flip bits in any order we like.

The only way to toggle a value on the edge of the matrix is by flipping the bit right next to it an uneven amount of times. As we're looking for the lowest possible flips, we want to flip it a maximum of 1 time. So, in a scenario like the on below, x will need to be flipped exactly once, and y will need to be flipped exactly 0 times.

. .
1 x
0 y
. ,

From this we can draw two conclusions:

1. A corner of the matrix can never be toggled—if a 1 on the corner is found it is not possible with any number of flips to make the matrix zero. Your first example can thus be discarded without even flipping a single bit.

2. A bit next to a corner must have the same same value as the bit on the other side. This matrix that you posted in a comment can thus as well be discarded without flipping a single bit (bottom right corner).

Two examples of the conditions above:

0 1 .
0 x .
. . .

Not possible, as x needs to be flipped exactly once and exactly zero times.

0 1 .
1 x .
. . . 

Possible, x needs to be flipped exactly once.

---

Algorithm

We can now make an recursive argument, and I propose the following:

1. We are given an m by n matrix.
2. Check the corner conditions above as stated above (i.e. corner != 1, bits next to corner has to be the same value). If either criteria are violated, return impossible.
3. Go around the edge of the matrix. If a 1 is encountered, flip the closest bit inside, and add 1 to the counter.
4. Restart now from #1 with a m - 2 by n - 2 matrix (top and bot row removed, left and right column) if either dimension is > 2, otherwise print the counter and quit.

---

Implementation

Initially I had thought this would turn out nice and pretty, but truth be told it is a little more cumbersome than I originally thought it would be as we have to keep track of a lot of indices. Please ask questions if you're wondering about the implementation, but it is in essence a pure translation of the steps 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', i.e. 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's 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;
}

---

Output

3 3
1 0 1
1 1 1
0 1 0

impossible

3 3
0 1 0
1 1 1
0 1 0

1

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