TopCoder SRM 297 Div1 Medium CageTheMonster

問題

hxwのグリッドで表される迷路がある。
'.'および'^'のマスは何もないマスで、'#'のマスは壁である。

この迷路の'^'のマスのどこかにモンスターを置く。
モンスターは迷路を上下左右の何もないマスに動くことができる。
迷路の外へモンスターが脱出できないように、魔法で壁を置く。

魔法で、一度につき一列または一行を全て壁にすることができる。
モンスターの初期位置が含まれる列または行は選ぶことができない。
魔法の壁は、最小で何回置かなければならないか、求めよ。

制約条件

h,w≦40

方針

モンスターの初期位置を一通り決めたとする。
モンスターより右側に壁を置く場合、その壁はモンスターの一つ右隣の列におくととしてよい。
同様に、4方向に壁を置く場合、その壁はモンスターの隣にあるとしてよい。

これを、全初期位置について、4方向に壁を置くかおかないか全通り試せばいい。

ソースコード

const int dy[]={-1,0,1,0}, dx[]={0,-1,0,1};
bool v[40][40];
bool dfs(int y,int x,int h,int w,vs &maze){
	if(y<0||x<0||y>=h||x>=w)return 1;
	if(v[y][x]||maze[y][x]=='#')return 0;
	v[y][x]=1;
	rep(d,4){
		int ny=y+dy[d], nx=x+dx[d];
		if(dfs(ny,nx,h,w,maze))return 1;
	}
	return 0;
}
class CageTheMonster {
	public:
	int capture(vector <string> labyrinth) 
	{
		vs maze=labyrinth;
		int h=maze.size(), w=maze[0].size();
		int ans=inf;
		
		rep(i,h)rep(j,w)if(labyrinth[i][j]=='^'){
			rep(mask,1<<4){
				maze=labyrinth;
				if((mask&1)&&j)rep(k,h)maze[k][j-1]='#';
				if((mask&2)&&j<w-1)rep(k,h)maze[k][j+1]='#';
				if((mask&4)&&i)rep(k,w)maze[i-1][k]='#';
				if((mask&8)&&i<h-1)rep(k,w)maze[i+1][k]='#';
				memset(v,0,sizeof(v));
				if(!dfs(i,j,h,w,maze))ans=min(ans,__builtin_popcount(mask));
			}
		}
		return ans==inf?-1:ans;
	}
};