SRM485 Div2 Hard(1000) RectangleAvoidingColoringEasy
盤面が大きい場合はrectangle-avoidingに塗ることができないので0を返す。小さい場合は探索。
#include <string> #include <vector> using namespace std; vector<string> B; int N, M; int BT() { for ( int a=0; a<N; a++ ) for ( int b=a+1; b<N; b++ ) for ( int c=0; c<M; c++ ) for ( int d=c+1; d<M; d++ ) if ( B[a][c]=='B' && B[a][d]=='B' && B[b][c]=='B' && B[b][d]=='B' || B[a][c]=='W' && B[a][d]=='W' && B[b][c]=='W' && B[b][d]=='W' ) return 0; int x = -1; int y = -1; for ( int i=0; i<N && x==-1; i++ ) for ( int j=0; j<M && x==-1; j++ ) if ( B[i][j] == '?' ) x = i, y = j; if ( x == -1 ) return 1; int r = 0; B[x][y] = 'B'; r += BT(); B[x][y] = 'W'; r += BT(); B[x][y] = '?'; return r; } class RectangleAvoidingColoringEasy{public: int count( vector <string> board ) { B = board; N = (int)board.size(); M = (int)board[0].size(); int large[] = { 0, 11, 11, 7, 7, 5, 5, 3, 3, 3, 3 }; if ( N >= large[M] ) return 0; else return BT(); }};