题目链接：hdu 4770 Lights Against Dudely

题目大意：在一个N*M的银行里，有N*M个房间，‘#’代表坚固的房间，‘.‘代表的是脆弱的房间，脆弱的房间个数不会超过15个，现在为了确保安全，要在若干个脆弱的房间上装灯，普通的灯是照亮{0, 0}, {-1, 0}, {0, 1}(和题目中坐标有点出入)，然后可以装一个特殊的，可以照射

• { {0, 0}, {0, 1}, {1, 0} },
• { {0, 0}, {-1, 0}, {0, -1} },
• { {0, 0}, {0, -1}, {1, 0} }
  同一个房间不可以装两栈灯，灯光不能照射坚固的房间，问说最少需要多少栈灯。

  解题思路：dfs+剪枝，暴力枚举放特殊灯的位置，然后将脆弱房间按照i坐标大放前面，相等的将j坐标小的方前面，这样做是为了dfs的时候剪枝，只要碰到一个房间不能放就返回。

  #include 
       
         #include 
        
          #include 
         
           using namespace std; const int maxn = 200; const int maxv = 20; const int INF = 0x3f3f3f3f; const int dir[4][3][2] = { { {0, 0}, {-1, 0}, {0, 1} }, { {0, 0}, {0, 1}, {1, 0} }, { {0, 0}, {-1, 0}, {0, -1} }, { {0, 0}, {0, -1}, {1, 0} } }; int ans; int n, N, M, x[maxv], y[maxv], c[maxv]; int v[maxn+5][maxn+5]; char g[maxn+5][maxn+5]; inline int judge (int xi, int yi, const int d[3][2]) { for (int i = 0; i < 3; i++) { int p = xi + d[i][0]; int q = yi + d[i][1]; if (p <= 0 || p > N) continue; if (q <= 0 || q > M) continue; if (g[p][q] == '#') return 0; } return 1; } inline void set (int xi, int yi, const int d[3][2], int type) { for (int i = 0; i < 3; i++) { int p = xi + d[i][0]; int q = yi + d[i][1]; if (p <= 0 || p > N) continue; if (q <= 0 || q > M) continue; v[p][q] = type; } } void init () { n = 0; for (int i = 1; i <= N; i++) scanf("%s", g[i] + 1); for (int i = N; i; i--) { for (int j = 1; j <= M; j++) { if (g[i][j] == '.') { x[n] = i; y[n] = j; n++; } } } memset(c, 0, sizeof(c)); for (int i = 0; i < n; i++) c[i] = judge(x[i], y[i], dir[0]); } /* int solve (int spi, int id) { memset(v, 0, sizeof(v)); int ans = INF; for (int s = 0; s < (1<
          
           = ans) return; if (d == n) { ans = cnt; return; } if (v[x[d]][y[d]]) dfs (d + 1, f, cnt); if (c[d] && d != f) { set(x[d], y[d], dir[0], 1); dfs (d + 1, f, cnt+1); set(x[d], y[d], dir[0], 0); } } int main () { while (scanf("%d%d", &N, &M) == 2 && N + M) { init(); ans = INF; if (n == 0) ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 4; j++) { if (judge (x[i], y[i], dir[j])) { memset(v, 0, sizeof(v)); set(x[i], y[i], dir[j], 1); dfs(0, i, 1); set(x[i], y[i], dir[j], 0); } } } if (ans == INF) printf("-1\n"); else printf("%d\n", ans); } return 0; }