SRM504 Div2 Hard(1000) Algrid

Algrid

次の行に移った時、前の行は出力と同じになっているはずなので、行ごとに辞書順最小の入力を求めれば良い。

マスごとに別の値を入れて問題通りに動かしてみる。その値が白か黒に塗られれば元の値はどちらでも良いので黒にする。塗られなければ、異動先の出力の色にする。

AlgridTwo（Div1の問題）ももっと簡単に解けたのか。

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

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

    vector<string> ans(H);
    ans[0] = output[0];

    for ( int y=1; y<H; y++ )
    {
        string t = "";
        for ( int x=0; x<W; x++ )
            t += char('a'+x);

        for ( int x=0; x<W-1; x++ )
        {
            if ( output[y-1][x]=='W' && output[y-1][x+1]=='W' )
                ;
            if ( output[y-1][x]=='B' && output[y-1][x+1]=='W' )
                t[x] = t[x+1] = 'B';
            if ( output[y-1][x]=='W' && output[y-1][x+1]=='B' )
                t[x] = t[x+1] = 'W';
            if ( output[y-1][x]=='B' && output[y-1][x+1]=='B' )
                swap(t[x],t[x+1]);
        }

        for ( int x=0; x<W; x++ )
            if ( ( t[x]=='B' || t[x]=='W' ) && t[x]!=output[y][x] )
                return vector<string>();

        for ( int x=0; x<W; x++ )
        {
            char c = 0;

            for ( int i=0; i<W; i++ )
            if ( t[i] == 'a'+x )
                c = output[y][i];
            if ( c == 0 )
                c = 'B';

            ans[y] += c;
        }
    }

    return ans;
}};