2089-Mysterious Dungeons

問題概要

部屋の情報が以下のように与えられる．

@	主人公の初期位置
	ゴール
小文字英字(a〜z)	同じ大文字英字("a"cなら"A"c)がOFFの場合ONにし，ONの場合はOFFにする
大文字英字(A〜Z)	初期状態ではONで，ONの場合は通行不能でOFFの場合しか通行可能
.	常に通行可能
#	常に通行できない

主人公がゴールに辿りつける場合は最短時間を，それ以外の場合は-1を出力せよ．

考え方

英字のONOFFの状態をbitで持ってBFSするだけ

実装(C++)

#include <vector>
#include <iostream>
#include <queue>
#include <bitset>
#include <map>
using namespace std;

int H,W,sx,sy;
vector<string> MAP;
struct state{
	int used;
	int x,y;
};
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool operator<(const state &a,const state &b){
	return a.x==b.x?(a.y==b.y?a.used<b.used:a.y<b.y):a.x<b.x;
}
bool operator>(const state &a,const state &b){
	return b<a;
}
int solve(){
	queue<state> que;
	map<state,short> turn;
	state t;
	t.x=sx;t.y=sy;t.used=int();
	que.push(t);
	turn.insert(make_pair(t,0));
	while(!que.empty()){
		t=que.front();que.pop();
		map<state,short>::iterator it=turn.find(t);
		//cout<<t.x<<","<<t.y<<","<<t.used<<endl;
		int now=(*it).second;
		for(int i=0;i<4;i++){
			int nx=t.x+dx[i],ny=t.y+dy[i];
			if(MAP[nx][ny]=='#')continue;
			if(MAP[nx][ny]=='<')return now+1;
			if(MAP[nx][ny]>='a'&&MAP[nx][ny]<='z'){
				state next;
				next.x=nx;next.y=ny;
				next.used=t.used^(1<<(MAP[nx][ny]-'a'));
				map<state,short>::iterator it2=turn.find(next);
				if(it2!=turn.end())continue;
				turn.insert(it2,make_pair(next,now+1));
				que.push(next);
			}else if((MAP[nx][ny]=='.')||(MAP[nx][ny]>='A'&&MAP[nx][ny]<='Z'&&(t.used&(1<<(MAP[nx][ny]-'A')))>0)){
				state next;
				next.x=nx;next.y=ny;
				next.used=t.used;
				map<state,short>::iterator it2=turn.find(next);
				if(it2!=turn.end())continue;
				turn.insert(it2,make_pair(next,now+1));
				que.push(next);
			}
		}
	}
	return -1;
}
int main() {
	for(;cin>>H>>W;){
		if(H==0)break;
		MAP.clear();
		for(int i=0;i<W;i++){
			string t;
			cin>>t;
			MAP.push_back(t);
		}

		for(int i=0;i<W;i++)for(int j=0;j<H;j++){
			if(MAP[i][j]=='@'){
				sx=i;sy=j;
				MAP[i][j]='.';
				break;
			}
		}
		cout<<solve()<<endl;
	}

	return 0;
}