TopCoder Open 2010 Qual3 Hard - simezi

問題概要

ガラスは幅W高さHの長方形で、カッターは最初(startX,startY)の座標にいる。

カッターの動かし方が次のような文字列で与えられるとき、カッターを動かした後でガラスが何枚のパーツに分かれたかを求めよ。

'U'：カッターを上へ動かす(y座標-1)
'D'：下へ(y座標+1)
'L'：左へ(x座標-1)
'R'：右へ(x座標+1)

W,H≦1000である。

解法

ガラスが1000x1000なのでカットをシミュレートして、カット後につながっているガラスを1枚として、枚数を数えればいい。
100万回のループは再帰で書くとスタックオーバーフローするので自前のループを使う。

カットのシミュレートの仕方の説明。
幅w高さhのガラスには（縁も含めて）縦線がw+1本、横線がh+1本書ける。
ので(w+1)*h個の縦方向の短い線分、(h+1)*w本の短い線分のそれぞれについて、切れ目が入ったか入ってないかを覚えておく。

具体的には、それぞれの線に0,1,...,wと0,1,...,hと番号をつけて、カッターの歯が(x,y)にいるときにカッターが各方向に動いたら、どの番号の線に切れ目が入るかがわかればよい。

(x,y)に居てUに動いたら、上からy-1番目、左からx番目の縦線に切れ目が入る
(x,y)に居てLに動いたら、上からy番目、左からx-1番目の横線に切れ目が入る

（以下同様。○番目というのは０から数えることに注意。）

解らなかったら手を動かして図を書いてみること。

これだけできれば後は、切れ目をまたがないように幅優先でガラスを辿っていけば繋がっているガラスの部分がわかる。

ソースコード

typedef vector<bool> vb;
int dy[]={-1,0,1,0},dx[]={0,-1,0,1};

class CuttingGlass {
	public:
	int pieces(int w, int h, int x, int y, vector &lt;string%gt; program) 
	{
		string pg=accumulate(all(program),string());
		
		vector<vb> tate(h,vb(w+1));
		vector<vb> yoko(h+1,vb(w));
		vector<vb> V(h,vb(w));
		
		//cut
		rp(i,pg)
		{
			if(pg[i]=='U')tate[--y][x]=1;
			else if(pg[i]=='D')tate[y++][x]=1;
			else if(pg[i]=='L')yoko[y][--x]=1;
			else yoko[y][x++]=1;
		}
		
		//fill & count
		int ans=0;
		rep(i,h)rep(j,w)if(!V[i][j])
		{
			ans++;
			
			V[i][j]=1;
			queue<pi> Q; Q.push(mp(i,j));
			while(!Q.empty())
			{
				int y=Q.front().first,x=Q.front().second;
				Q.pop();
				
				rep(d,4)
				{
					int ny=y+dy[d],nx=x+dx[d];
					if(ny<0||nx<0||ny>=h||nx>=w)continue;
					if(d==0&&yoko[y][x]||d==1&&tate[y][x]||
				d==2&&yoko[y+1][x]||d==3&&tate[y][x+1])continue;
					
					if(!V[ny][nx])
					{
						V[ny][nx]=1;
						Q.push(mp(ny,nx));
					}
				}
			}
		}
		return ans;
	}
};