c++ - 通过翻转单元格组用零填充二维数组

Question

有一个问题，我需要用零填充一个数组，假设如下:

• 数组中只能有0和1
• 我们只能将0更改为1，将1更改为0
• 当我们在数组中遇到 1 时，我们必须将其更改为 0，这样它的邻居也会更改，例如，对于如下数组:

1 0 1
1 1 1
0 1 0

当我们改变 (1,1) 处的元素时，我们得到这样的数组:

1 1 1
0 0 0
0 0 0

• 我们不能改变第一行
• 我们只能改变数组中的元素
• 最终结果是我们必须将 1 更改为 0 以使数组清零的次数

1)第一个例子，数组如下:

0 1 0
1 1 1
0 1 0

答案是 1。

2) 第二个例子，数组如下:

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。

也可能存在无法将数组归零的情况，那么答案应该是“不可能”。

不知何故，我不能让它工作:对于第一个例子，我得到了正确的答案 (1) 但对于第二个例子，程序说 impossible 而不是 10。

知道我的代码有什么问题吗？

#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

我相信您的程序在 6x8 矩阵中返回不可能 的原因是因为您一直以从左到右/从上到下的方式遍历，将遇到的每个 1 实例替换为 0 . 尽管这似乎是正确的解决方案，但它所做的只是通过修改矩阵的相邻值将 1 和 0 散布在矩阵周围。我认为解决这个问题的方法是从下到上/从右到左并将 1 推向第一行。以某种方式逼近(诱捕)他们，直到他们被淘汰。

无论如何，这是我对这个问题的解决方案。我不完全确定这是否是您想要的，但我认为它可以完成您提供的三个矩阵的工作。代码不是很复杂，最好用一些更难的问题来测试它，看看它是否真的有效。

#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);
    }
}

ma​​trix1 的输出:

-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 

ma​​trix2 的输出:

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

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

Num of flips = 1

ma​​trix3 的输出:

-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 

ma​​trix4 的输出(解决您的原始问题):

-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