2013 TCO Round 1B Medium(500) EllysFigurines

EllysFigurines

少なくともこの列は消すという列を決めれば、貪欲に左から消すことで最小回数が求められる。行も同様。また、消す列を決めれば、残った像がいる行を消さなければいけない。消す列を全探索する。

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

int f( string S, int R )
{
    int n = (int)S.length();
    int c = 0;
    for ( int i=0; i<n; i++ )
    if ( S[i]=='X' )
    {
        for ( int j=0; j<R; j++ )
        if ( i+j<n )
            S[i+j] = '.';
        c++;
    }
    return c;
}

class EllysFigurines{public:
int getMoves( vector <string> board, int R, int C )
{
    int w = (int)board[0].length();
    int h = (int)board.size();
    int ans = w+h;

    for ( int b=0; b<(1<<w); b++ )
    {
        string Sx;
        for ( int x=0; x<w; x++ )
            Sx += ".X"[b>>x&1];

        string Sy;
        for ( int y=0; y<h; y++ )
        {
            bool f = false;
            for ( int x=0; x<w; x++ )
                if ( (b>>x&1)==0 && board[y][x]=='X' )
                    f = true;
            Sy += f ? "X" : ".";
        }

        ans = min( ans, f(Sx,C)+f(Sy,R) );
    }

    return ans;
}};