hdu 4770 Lights Against Dudely(폭력 검색)

이 문제의 관건은 밝게 밝혀야 할 방이 최대 15개에 불과하기 때문에 이 15개의 점을 폭력적으로 매거할 수 있는 상태이다. 2^15=32768은 아주 작은 수이다.
매거된 프로그램은 귀속적이라고 생각하기 쉽다. 귀속만 지수급의 상태가 생기기 때문에 for순환은 다항식 단계일 뿐이다.
시계 방향으로dir방향수조를 만들면 많은 코드를 절약할 수 있다.
매거할 때 먼저 특수등을 고려하지 않고 일반등만 있고 불을 놓지 않는 상태를 매거한다.
매거적인 사고방식은 이 상태가 #에 비쳤는지 아닌지를 판단하는 것이다. 이 15개 점을 두루 훑어보면 #이 있으면 방안이 합법적이지 않다.
그리고 모든 점이 찍혔는지 아닌지를 판단하고, 모든 점에 대해 모든 점을 두루 훑어보며 그것을 찍을 수 있는지 없는지를 본다.만약 점이 하나 있다면, 모든 점이 그것을 비출 수 없고, 방안도 합법적이지 않다.
합법적이면 갱신해.
그리고 특수등을 생각해.
특수등을 세 가지 등으로 보고 각각 세 방향에 대응하는 것이 쓰기 쉽다.
매 점을 이 세 가지 특수등으로 바꾸는 상태가 합법적인지, 합법적으로 갱신된다면.
코드:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int N,M,Num;
struct node{
	int x,y;
	int p;
}G[20];
int dir[5][2]={{0,0},{-1,0},{0,1},{1,0},{0,-1}};
int res;
int Map[205][205];
bool check2(int i){
    for(int k=1;k<=Num;k++){
			int j=G[k].p;
			if(j==0) continue;
			int tx1=G[k].x+dir[j][0];
			int ty1=G[k].y+dir[j][1];
			if(tx1==G[i].x&&ty1==G[i].y) return 1;
			if(j==4) j=1;
			else j++;
			int tx2=G[k].x+dir[j][0];
			int ty2=G[k].y+dir[j][1];
			if(tx2==G[i].x&&ty2==G[i].y) return 1;
	} 
	return 0;
}
	
bool check(){
	for(int i=1;i<=Num;i++){
		int j=G[i].p;
		if(j==0) continue;
		int tx1=G[i].x+dir[j][0];
		int ty1=G[i].y+dir[j][1];
		if(j==4) j=1;
		else j++;
		int tx2=G[i].x+dir[j][0];
		int ty2=G[i].y+dir[j][1];
		if(Map[tx1][ty1]||Map[tx2][ty2]) return 0;
		
	}
	
	for(int i=1;i<=Num;i++){
		if(G[i].p>=1) continue;
		if(!check2(i)) return 0; 
	}
	return 1;
}
void f(int x){
	if(x==Num+1){
		if(check()){
			int tmp=0;
			for(int i=1;i<=Num;i++){
				if(G[i].p>=1) tmp++;
			}
			res=min(res,tmp);
		}
 
		for(int i=1;i<=Num;i++){
			
			int t=G[i].p;
			for(int j=2;j<=4;j++){
				G[i].p=j;
				if(check()){
					int tmp=0;
					for(int k=1;k<=Num;k++){
						if(G[k].p>=1)tmp++;
					}
					
					res=min(res,tmp);
				}
			}
			G[i].p=t;
		}
		return ;
	}
	for(int i=0;i<=1;i++){
		G[x].p=i;
		f(x+1);
	}
}

int main(){
	while(~scanf("%d%d",&N,&M)){
		if(!N&&!M) break;
		Num=0;
		memset(Map,0,sizeof(Map));
		memset(G,0,sizeof(G));
		char ch;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=M;j++){
				scanf(" %c", &ch);
				if(ch=='#'){
					Map[i][j]=1;
				}
				else if(ch=='.'){
				
					Map[i][j]=0;
					G[++Num].x=i;
					G[Num].y=j;
					G[Num].p=0;
				}
			}
		}

		res=1000;
		if(Num==0){
			cout<<0<<endl;
			continue;
		}
		f(1);
		if(res==1000) res=-1;
		cout<<res<<endl;
	}
	return 0;
}