SRM504 Div1 Medium(500) AlgridTwo

AlgridTwo

次の行に移った時、前の行は出力と同じになっているはずなので、行ごとに何通りの入力があるかを求めて掛け合わせればよい。
行ごとのありうる入力の個数は動的計画法で求める。あるマスの１つ前まで処理を行って、そのマスが白や黒になった場合に何通りかをそれぞれ覚えておく。

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

class AlgridTwo{public:
int makeProgram( vector <string> output )
{
    int M = 1000000007;
    int H = (int)output.size();
    int W = (int)output[0].size();

    long long ans = 1;
    
    for ( int y=1; y<H; y++ )
    {
        //  ここより前の処理で色が白/黒になる場合、以降何通りの入力がありうるか
        long long w, b;
        if ( output[y][W-1]=='W' )
            w=1, b=0;
        else
            b=1, w=0;

        for ( int x=W-2; x>=0; x-- )
        {
            long long nw = w;
            long long nb = b;

            if ( output[y-1][x]=='W' && output[y-1][x+1]=='W' )
            {
                if ( output[y][x]=='W' )  w = nw+nb,  b = 0;
                if ( output[y][x]=='B' )  b = nb+nw,  w = 0;
            }
            if ( output[y-1][x]=='B' && output[y-1][x+1]=='W' )
            {
                if ( output[y][x]=='W' )  w = b = 0;
                if ( output[y][x]=='B' )  w = b = nb*2;
            }
            if ( output[y-1][x]=='W' && output[y-1][x+1]=='B' )
            {
                if ( output[y][x]=='W' )  w = b = nw*2;
                if ( output[y][x]=='B' )  w = b = 0;
            }
            if ( output[y-1][x]=='B' && output[y-1][x+1]=='B' )
            {
                w = nw,  b = nb;
            }

            w %= M;
            b %= M;
        }

        ans = ans * (w+b) % M;
    }

    return (int)ans;
}};