SRM 504 500pt: AlgridTwo

keyword

シミュレーション　C++

問題概要

次の関数Algrid2がある。

vector<string> Algrid2(vector<string> input){
    int H = input.size(), W = input[0].size();
    for(int i=0; i<H-1; i++)for(int j=0; j<W-1; j++){
        char A = input[i][j], input[i][j+1];
        if(A=='W' && B=='W'){
            ;
        }
        else if(A=='B' && B=='W'){
            input[i+1][j] = input[i+1][j+1] = 'B';
        }
        else if(A=='W' && B=='B'){
            input[i+1][j] = input[i+1][j+1] = 'W';
        }
        else{
            swap(input[i+1][j], input[i+1][j+1]);
        }
    }
    return input;
}

output=Algrid2(input)となるようなinputの個数をmodで求める問題。

解法

2行目以降でシミュレーションっぽいことをしたら求められる。

class AlgridTwo {
public:
int makeProgram(vector <string> output) {
	int ret = 1;
	int H = output.size(), W = output[0].size();
	for(int i=0; i<H-1; i++){
		string t = string(W, '?');
		for(int j=0; j<W-1; j++){
			char A = output[i][j], B = output[i][j+1];
			if(A=='B' && B=='B'){
				swap(t[j],t[j+1]);
			}
			else if(A=='W' && B=='B'){
				t[j] = t[j+1] = 'W';
			}
			else if(A=='B' && B=='W'){
				t[j] = t[j+1] = 'B';
			}
		}
		for(int j=0; j<W; j++)if(t[j]!='?'){
			if(t[j] != output[i+1][j]) return 0;
			else ret = (ret*2)%MOD;
		}
	}

	return ret%MOD;
}