硬币翻转游戏:优化问题

Question

有一个矩形的硬币网格,其中头部由值1表示,尾部由值0表示.您使用2D整数数组表(1到10行/列,包括1和10行)来表示.

在每次移动中,您选择网格中的任何单个单元格(R,C)(第R行,第C列)并翻转所有单元格中的硬币(r,c),其中r介于0和R之间,包括,c介于0和C之间,包括0和C. 翻转硬币意味着将单元格的值从零反转为一或一到零.

返回将网格中的所有单元格更改为尾部所需的最小移动次数.这将永远是可能的.

例子:

1111  
1111  
returns: 1  

01  
01  
returns: 2   

010101011010000101010101  
returns: 20  

000  
000  
001  
011  
returns: 6  

这就是我所尝试的:由于翻转的顺序并不重要,并且两次移动硬币就像完全没有移动一样,我们可以找到翻转硬币的所有不同组合,并最小化硬币的大小组合(意思是那些给出所有尾巴的组合).

这可以通过制作一个由所有硬币组成的集合来完成,每个硬币由一个索引表示.(即如果总共有20个硬币,这个集合将包含20个元素,给它们索引1到20).然后制作所有可能的子集,看看它们中的哪一个给出答案(即,如果在子集中的硬币上移动给我们所有的尾巴).最后,最小化良好组合的大小.

我不知道我是否能够过于清楚地表达自己...如果你愿意,我会发一个代码.无论如何,这种方法太耗费时间和浪费,并且对于大于20的硬币(在我的代码中)是不可能的.怎么去这个？

Answer 1

我认为贪婪算法就足够了,每枚硬币只需一步.

每一个动作都会翻转一个矩形的棋盘子集.有些硬币包含在比其他子集更多的子集中:左上角(0,0)的硬币位于每个子集中,右下角的硬币只有一个子集,即包含每个硬币的硬币.

因此,选择第一步是显而易见的:如果必须翻转右下角,则翻转每一枚硬币.消除可能的行动.

现在,左下方硬币的近邻,左侧和上方,只能通过一次剩余的移动来翻转.因此,如果必须执行此移动,请执行此操作.邻居的评估顺序无关紧要,因为它们并不是彼此的真正替代品.但是,光栅图案应该足够了.

重复直到完成.

这是一个C++程序:

#include <iostream>
#include <valarray>
#include <cstdlib>
#include <ctime>
using namespace std;

void print_board( valarray<bool> const &board, size_t cols ) {
    for ( size_t i = 0; i < board.size(); ++ i ) { 
        cout << board[i] << " "; 
        if ( i % cols == cols-1 ) cout << endl;
    }   
    cout << endl;
}

int main() {
    srand( time(NULL) );
    int const rows = 5, cols = 5;

    valarray<bool> board( false, rows * cols );
    for ( size_t i = 0; i < board.size(); ++ i ) board[i] = rand() % 2;
    print_board( board, cols );

    int taken_moves = 0;
    for ( size_t i = board.size(); i > 0; ) { 
        if ( ! board[ -- i ] ) continue;

        size_t sizes[] = { i%cols +1, i/cols +1 }, strides[] = { 1, cols };

        gslice cur_move( 0, valarray<size_t>( sizes, 2 ),
                            valarray<size_t>( strides, 2 ) );
        board[ cur_move ] ^= valarray<bool>( true, sizes[0] * sizes[1] ); 

        cout << sizes[1] << ", " << sizes[0] << endl;
        print_board( board, cols );

        ++ taken_moves;
    }   

    cout << taken_moves << endl;
}