1220-The Devil of Gravity

問題概要

悪魔のエディタを作った男が居た．

悪魔のエディタは次の独特の機能を持っている．

1. 文字列(空白を持たない連続した文字の並び)の下に何も文字列が無い場合，その文字列は落下する．下に文字列がある状態になるか，一番下に辿り付くまで落下は継続する．
2. 同じ行にある二つの文字列が隣接した場合は，連結して一つの文字列となる．

例えば，

abcdef  ghijkl
     mnop
qrstuvw

から，mnopを消去すると

abcdef
qrstuvw ghijkl

のようになる．
これの一番下の行の二つの文字列の間にxを加えると

abcdef
qrstuvwxghijkl

となる．

一般に，何かコマンドを実行したら，次のルールが適用される．
ただし，Sは文字列とし，left(S)は文字列の左端のカラム番号，right(S)は文字列の右端のカラム番号
，そしてrow(S)はSのある行の番号(下からの番号)とする．

1. row(S)-1行目のleft(S)からright(S)の間に文字列が無い場合，Sはrow(S)-1行目に移動する．これは条件を満たさなくなるか，row(S)=0になるまで実行される．
2. 二つの文字列S,Tが同じ行にあり，right(S)+1=left(T)の場合二つの文字列は連結され，一つの文字列になる．もちろん行は移動したりしない．

文字列はかならず，一つ以上の文字を含むことと，最初のルールの適用が完全に終わった後で2番目のルールが適用されることに気を付けろ．
例えば

   dddddddd
   cccccccc
bbbb
aaa

において，bbbbの右端のbを消去した場合，"bbb"と"ccccccccc"が連結することはなく，"aaa"と"ccccccccc"が連結される．

悪魔のエディタにはカーソルが存在し，それは常に一つの文字列(これを現在の文字列という)を差す．カーソルは文字列のどれかの文字か，文字列の末尾を差す．カーソルは文字列を支えるのに使えないことに注意せよ．例えば，先程の例のbbbbの一番最後にカーソルが居たとしても結果は変わらず，最終的にdの左端を差すことになる．

悪魔のエディタは以下の1文字の英数字で表わされるコマンドを受け付ける

• F カーソルを一つ後ろに進める．もし，文字列の末尾を差していた場合エラーとなる．
• B カーソルを一つ前に進める．もし，文字列の先頭を差していた場合エラーとなる．
• P カーソルを一つ上に進める．カーソルの位置が不正になった場合はエラーとなる．
• N カーソルを一つ下に進める．カーソルが一番下の行に入るか，カーソルの位置が不正になった場合エラーとなる．現在の文字列の始めもカーソルの位置も変化しません．現在の文字列が空になる場合，一つ下の行に移動します．
• D カーソルの位置にある文字を消去する．もし，カーソルが末尾を差している場合エラーとなる．その文字を消したことにより，現在の文字列が落下するならば，カーソルも一緒に落下する．現在の文字列の全てが消える場合カーソルは一つ下に落下する．
• C 一文字の文字列を現在のカーソルの上に作成する．その文字は現在カーソルが差している文字となる．もし，カーソルが末尾を差している場合エラーとなる．また，既に文字列が存在した場合もエラーとなる．コマンド実行後カーソルは上に1つ，右に1つ進行する．
• 小文字英字と数字が入力された場合，現在のカーソルの位置にその文字を挿入する．カーソルは一文字後ろに移動し，文字列の最初のカラムが変化することは無い．

エラーが起きた場合は，そのままエディタは不正終了する．

あなたの仕事はこの悪魔のエディタを実装することである．

入力

最初の行にテストケースの個数が与えられる．
各テストケースは一行からなり，
コマンドの文字列(100文字以下)が与えらえる．
コマンドの最初は初期の文字列からなり，この文字列の末尾をカーソルは差すことになる．

出力

各テストケースについて，
現在の文字列を一行に出力せよ．途中でエラーが発生した場合は"ERROR"と出力せよ．

解法

実装する

実装(C++)

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
char MAP[201][201];
int curX,curY;
string cmd;
bool hasError=false;
const int W=201,H=10;
#define REP(i,x)for(int i=0;i<(int)x;i++)
void init(){
	curX=0,curY=0;
	memset(MAP,' ',sizeof(MAP));
	hasError=false;
}
void show(){
	cout<<"----"<<endl;
	cout<<curX<<","<<curY<<endl;
	for(int y=H-1;y>=0;y--){
		REP(x,W){
			cout<<MAP[x][y];
		}
		cout<<endl;
	}
}
void addChar(char t){
	int x=curX;
	while(MAP[x][curY]!=' ')x++;
	for(int tx=x;tx>curX;tx--){
		MAP[tx][curY]=MAP[tx-1][curY];
	}
	MAP[curX][curY]=t;
	curX++;
}
void forward(){
	if(MAP[curX][curY]==' ')hasError=true;
	curX++;
}
void back(){
	if(curX==0||MAP[curX-1][curY]==' ')hasError=true;
	curX--;
}
bool isOk(int x,int y){
	if(MAP[x][y]!=' '||(x>0&&MAP[x-1][y]!=' '))return true;
	return false;
}
//一つ上に進める
void P(){
	if(isOk(curX,curY+1)){
		curY++;
	}else{
		hasError=true;
	}
}
void N(){
	if(curY>0&&isOk(curX,curY-1)){
		curY--;
	}else{
		hasError=true;
	}
}
void createNewColumn(){
	if(MAP[curX][curY]==' '){
		hasError=true;
	}
	if(MAP[curX][curY+1]!=' '){
		hasError=true;
	}
	MAP[curX][curY+1]=MAP[curX][curY];
	curX++;
	curY++;
}
void D(){
	if(MAP[curX][curY]==' '){
		hasError=true;return;
	}
	//全部消えるかの判定
	if(MAP[curX+1][curY]==' '){
		if((curX>0&&MAP[curX-1][curY]==' ')||curX==0){
			MAP[curX][curY]=' ';
			curY--;
			if(curY<0){
				hasError=true;
			}
		}else{
			int tX=curX;
			while(MAP[tX][curY]!=' '){
				MAP[tX][curY]=MAP[tX+1][curY];
				tX++;
			}
		}
	}else{
		int tX=curX;
		while(MAP[tX][curY]!=' '){
			MAP[tX][curY]=MAP[tX+1][curY];
			tX++;
		}
	}
}
bool can(int sx,int ex,int y){
	for(int x=sx;x<ex;x++){
		if(MAP[x][y]!=' ')return false;
	}
	return true;
}
void word_down(){
	bool update=false;
	do{
		update=false;
		for(int y=H-1;y>0;y--){
			REP(x,W){
				if(MAP[x][y]==' ')continue;
				int tx=x;
				while(MAP[tx][y]!=' ')tx++;
				int tar_y=y;
				for(int ty=y-1;ty>=0;ty--){
					if(!can(x,tx,ty)){
						break;
					}else{
						tar_y=ty;
					}
				}
				if(tar_y!=y){
					for(int qx=x;qx<tx;qx++){
						MAP[qx][tar_y]=MAP[qx][y];
						MAP[qx][y]=' ';
					}
					update=true;
				}
				x=tx-1;
			}
		}
	}while(update);
}
void solve(){
	init();
	REP(i,cmd.size()){
		//cout<<cmd[i]<<endl;
		//show();
		if(hasError)break;
		char now=cmd[i];
		if(islower(now)||isdigit(now)){
			addChar(now);
		}else{
			switch(now){
			case 'C':
				createNewColumn();
				break;
			case 'F':
				forward();
				break;
			case 'B':
				back();
				break;
			case 'P':
				P();
				break;
			case 'N':
				N();
				break;
			case 'D':
				D();
				break;
			default:
				break;
			}
		}
		word_down();
		while(curY>0&&MAP[curX][curY]==' '&&(curX==0||MAP[curX-1][curY]==' '))curY--;
	}
	//show();
	if(hasError){
		cout<<"ERROR"<<endl;
	}else{
		//cout<<":";
		while(true){
			if(curX&&MAP[curX][curY]!=' '&&MAP[curX-1][curY]==' ')break;
			if(curX==0)break;
			curX--;
		}
		while(MAP[curX][curY]!=' ')cout<<MAP[curX++][curY];
		cout<<endl;
	}
}

int main() {
	int T;
	cin>>T;
	while(T--){
		cin>>cmd;
		solve();
		//show();
	}

	return 0;
}