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

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矩阵中不可能返回的原因是因为你一直在以从左到右/从上到下的方式遍历,用0替换你遇到的每个1的实例.虽然这可能看起来像是正确的解决方案它所做的就是通过修改它的相邻值来分散矩阵周围的1和0.我认为解决这个问题的方法是从下到上/从右到左开始并将1s推向第一行.在某种程度上转弯(捕捉)它们直到它们被消除.

无论如何,这是我解决这个问题的方法.我不完全确定这是否是您要追求的,但我认为它可以完成您提供的三个矩阵的工作.代码不是很复杂,用一些更难的问题来测试代码是否真的很好.

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

矩阵1的输出:

-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 

矩阵2的输出:

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

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

Num of flips = 1

矩阵3的输出:

-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 

matrix4的输出(解决您的原始问题):

-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

如果 tab[0][j] 为 1，则必须切换 tab[1][j] 将其清除。然后，您无法在不清除第 0 行的情况下切换第 1 行。因此，这似乎是一个减少步骤。重复该步骤，直到剩下一行。如果最后一行运气不好的话，我的直觉是这是“不可能”的情况。

#include <memory>

template <typename Elem>
class Arr_2d
  {
  public:

    Arr_2d(unsigned r, unsigned c)
      : rows_(r), columns_(c), data(new Elem[rows_ * columns_]) { }

    Elem * operator [] (unsigned row_idx)
      { return(data.get() + (row_idx * columns_)); }

    unsigned rows() const { return(rows_); }
    unsigned columns() const { return(columns_); }

  private:
    const unsigned rows_, columns_;
    std::unique_ptr<Elem []> data;
  };

inline void toggle_one(bool &b) { b = !b; }

void toggle(Arr_2d<bool> &tab, unsigned row, unsigned column)
  {
    toggle_one(tab[row][column]);

    if (column > 0)
      toggle_one(tab[row][column - 1]);

    if (row > 0)
      toggle_one(tab[row - 1][column]);

    if (column < (tab.columns() - 1))
      toggle_one(tab[row][column + 1]);

    if (row < (tab.rows() - 1))
      toggle_one(tab[row + 1][column]);
  }

int solve(Arr_2d<bool> &tab)
  {
    int count = 0;
    unsigned i = 0;

    for ( ; i < (tab.rows() - 1); ++i)
      for (unsigned j = 0; j < tab.columns(); ++j)
        if (tab[i][j])
          {
            toggle(tab, i + 1, j);
            ++count;
          }

    for (unsigned j = 0; j < tab.columns(); ++j)
      if (tab[i][j])
        // Impossible.
        return(-count);

    return(count);
  }

unsigned ex1[] = {
0, 1, 0,
1, 1, 1,
0, 1, 0
};

unsigned ex2[] = {
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
};

Arr_2d<bool> load(unsigned rows, unsigned columns, const unsigned *data)
  {
    Arr_2d<bool> res(rows, columns);

    for (unsigned i = 0; i < rows; ++i) 
      for (unsigned j = 0; j < columns; ++j)
        res[i][j] = !!*(data++);

    return(res);
  }

#include <iostream>

int main()
  {
    {
      Arr_2d<bool> tab = load(3, 3, ex1);
      std::cout << solve(tab) << '\n';
    }

    {
      Arr_2d<bool> tab = load(6, 8, ex2);
      std::cout << solve(tab) << '\n';
    }

    return(0);
  }