SRM485 Div1 Medium(500) RectangleAvoidingColoring

RectangleAvoidingColoring

Div2より最大サイズが大きいので、そのままでは幅が1と2の場合が間に合わない。幅が1の場合は任意の色が塗れるので?の個数をcとして2^c。幅が2の場合は、WWとBBという塗り方を高々1つ含みそれ以外はWBかBWと塗る方法の個数を動的計画法で求める。

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> B;
int N, M;

long long One()
{
    return 1ll << count( B.begin(), B.end(), "?" );
}

long long Two()
{
    vector<long long> T(4);
    //  0:無し　1:WW　2:BB　3:WW,BB
    T[0] = 1;

    for ( int i=0; i<N; i++ )
    {
        vector<long long> P = T;
        T = vector<long long>(4);

        if ( ( B[i][0]=='?' || B[i][0]=='W' ) &&
             ( B[i][1]=='?' || B[i][1]=='W' ) )
            T[1] += P[0],  T[3] += P[2];

        if ( ( B[i][0]=='?' || B[i][0]=='B' ) &&
             ( B[i][1]=='?' || B[i][1]=='B' ) )
            T[2] += P[0],  T[3] += P[1];

        if ( ( B[i][0]=='?' || B[i][0]=='W' ) &&
             ( B[i][1]=='?' || B[i][1]=='B' ) )
            T[0] += P[0],  T[1] += P[1],  T[2] += P[2],  T[3] += P[3];

        if ( ( B[i][0]=='?' || B[i][0]=='B' ) &&
             ( B[i][1]=='?' || B[i][1]=='W' ) )
            T[0] += P[0],  T[1] += P[1],  T[2] += P[2],  T[3] += P[3];
    }

    return T[0] + T[1] + T[2] + T[3];
}

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;

    long long r = 0;
    B[x][y] = 'B';
    r += BT();
    B[x][y] = 'W';
    r += BT();
    B[x][y] = '?';

    return r;        
}

class RectangleAvoidingColoring{public:
long long count( vector <string> board )
{
    B = board;
    N = (int)board.size();
    M = (int)board[0].size();

    //  N >= Mにする
    if ( N < M )
    {
        vector<string> T( M, string( N, ' ' ) );
        for ( int i=0; i<M; i++ )
        for ( int j=0; j<N; j++ )
            T[i][j] = B[j][i];
        return count( T );
    }

    if ( M == 1 )
        return One();
    else if ( M == 2 )
        return Two();
    else if ( N >= 7  ||  M >= 7 )
        return 0;
    else
        return BT();
}};