2013 TCO Round 1B Medium(500) 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; }};