TopCoder SRM 736 Div2 Hard MazeWithKeys

これ本番の時間内だと綺麗に書けなさそう。
http://community.topcoder.com/stat?c=problem_statement&pm=14944

問題

２次元グリッドで構成される迷路を考える。
各セルは以下のいずれかである。

• 移動可能な空きマス
• 移動不可能な壁
• ゴール
• 移動可能な空きマスの上に、あるカギが置かれている
• 鍵のかかったドア

一旦カギを取得すると、対応するドアは移動可能になる。
この迷路で、隣接マスを辿り、必要ならカギを取得してドアを開け、ゴールに移動することを考える。

迷路のスタート位置は明確になっていない。
空きマスのどこかをスタート位置にすることにする。
この時、最低１回カギを使うことでゴールに到達できるスタート位置は何通りか。

解法

実際に全空きマスをスタート地点とし、

• ドアを開けることを許容したときゴール可
• ドアを開けることを許容しないときゴール不可

となる頂点を数え上げよう。

前者は変形したBFSで解ける。
隣接マスを徐々に辿るのは普通のBFSと一緒だが、カギとドアに関して少し工夫する。
もしドアに到達したときカギを未取得なら、そのドアマスには進入させない。
ただしその後対応するカギマスに進入した場合、ドアマスにも改めて進入させるようにする。

class MazeWithKeys {
	public:
	int H,W;
	vector<string> S;
	int vis[51][51];
	int key[26];
	int door[26];
	int ok(int sy,int sx,int use_door) {
		ZERO(vis);
		ZERO(key);
		MINUS(door);
		queue<int> Q;
		Q.push(sy*100+sx);
		
		while(Q.size()) {
			int cy=Q.front()/100;
			int cx=Q.front()%100;
			Q.pop();
			if(S[cy][cx]=='*') return 1;
			if(vis[cy][cx]) continue;
			vis[cy][cx]=1;
			int d[4]={1,0,-1,0};
			int i;
			FOR(i,4) {
				int ty=cy+d[i];
				int tx=cx+d[i^1];
				if(tx<0 || tx>=W || ty<0 || ty>=H) continue;
				if(vis[ty][tx] || S[ty][tx]=='#') continue;
				if(S[ty][tx]>='A' && S[ty][tx]<='Z') {
					door[S[ty][tx]-'A']=ty*100+tx;
					if(use_door && key[S[ty][tx]-'A']) Q.push(ty*100+tx);
				}
				else {
					if(S[ty][tx]>='a' && S[ty][tx]<='z') {
						key[S[ty][tx]-'a']++;
						if(use_door && door[S[ty][tx]-'a']>=0) Q.push(door[S[ty][tx]-'a']);
					}
					Q.push(ty*100+tx);
				}
				
			}
			
		}
		return 0;
	}
	
	int startingPoints(vector <string> a) {
		S=a;
		H=a.size();
		W=a[0].size();
		
		int y,x;
		int ret=0;
		FOR(y,H) FOR(x,W) if(S[y][x]=='.' && ok(y,x,1) && ok(y,x,0)==0) ret++;
		return ret;
	}
}

まとめ

本番意外に正答者は少ない。