StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think a greedy algorithm suffices, with one step per coin.</p> <p>Every move flips a rectangular subset of the board. Some coins are included in more subsets than others: the coin at (0,0) upper-left is in every subset, and the coin at lower-right is in only one subset, namely the one which includes every coin.</p> <p>So, choosing the first move is obvious: flip every coin if the lower-right corner must be flipped. Eliminate that possible move.</p> <p>Now, the lower-right coin's immediate neighbors, left and above, can only potentially be flipped by a single remaining move. So, if that move must be performed, do it. The order of evaluation of the neighbors doesn't matter, since they aren't really alternatives to each other. However, a raster pattern should suffice.</p> <p>Repeat until finished.</p> <p>Here is a C++ program:</p> <pre><code>#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; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload