SRM485 Div2 Hard(1000) RectangleAvoidingColoringEasy

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();
}};