SRM544 Div1 Medium(500) FlipGame - kusano

貪欲に裏返していく。ある行の最右の1の右隣は必ず通らなければいけない。

#include <string>
#include <vector>
using namespace std;

class FlipGame{public:
int minOperations( vector <string> board )
{
    int w = (int)board[0].size();
    int h = (int)board.size();

    int c = 0;

    while ( true )
    {
        int cx = 0;
        for ( int y=0; y<h; y++ )
        {
            for ( int x=w; x>cx; x-- )
                if ( board[y][x-1]=='1' )
                {
                    cx = x;
                    break;
                }
            
            for ( int x=0; x<cx; x++ )
                board[y][x] ^= 1;
        }

        if ( cx==0 )
            break;

        c++;
    }

    return c;
}};