题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4770
题目大意是让你放一些灯照亮一些房间 灯不可以照到某些特殊房间 但可以照出边界 灯光必须覆盖所有可以放灯的房间 求至少需要多少灯
搜索题
应该注意到冗长而无聊的题面中有告诉你最多只有15个可以放灯的房间
所以2^15来枚举
还应该注意到冗长而无聊的题面中有告诉你最多只有1个灯可以转向
所以还应该枚举哪个灯来转向
转向再枚举4个方向
然后判断是否成立
为了简化问题 单独把那些可放灯空间拿出来 最多15个
第一层循环枚举状态 2^15
第二层枚举哪个灯用来转向 15
然后就先判断所有的非转向灯会不会照得不该照到的房间
第三层枚举转向灯的四个方向
确定转向灯防止合法以后
检查当前灯光是否已经覆盖所有应该被照亮的房间（我用set）
这题去年前前后后写了三次 每一次都是连个完整程序都写不出
刚刚默默敲了1个小时然后编译AC一次过 竟然有一种报了世仇的快感...
回想起来以前写不出大概有两个原因
1.模拟题没有写子函数的习惯 然后循环嵌套一多就容易把自己写乱
而子函数judge可以随时返回 如果全部写再main里面就需要列好多flag 更容易写乱
2.没有把问题进行足够的抽象 第一次不说 如果后来能够意识到无非就是“15个格子的状态的搜索” 也许写起来就不会那么怵
1000ms的题目我920ms压线过实在惭愧
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <set> #include <stack> #include <queue> #include <vector> #include <cmath> #include <map> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; typedef struct { int x, y; }Node; const int maxn = 210; const int walk[][2] = {1, 0, 0, 1, -1, 0, 0, -1}; int n, m; char a[maxn][maxn]; Node v[20]; bool judge(int s, int sum, int turnid) { int vid = 0; set<P> check; for(int i = 0; i < sum; i++) //确定非转向灯是否能合法放置 并记录他们所能照亮的房间 { if(s & (1 << i) && i != turnid) { if(v[i].x - 1 >= 1 && v[i].x - 1 <= n && a[v[i].x - 1][v[i].y] != '.') return 0; if(v[i].y + 1 >= 1 && v[i].y + 1 <= m && a[v[i].x][v[i].y + 1] != '.') return 0; check.insert(P(v[i].x, v[i].y)); if(v[i].x - 1 >= 1) check.insert(P(v[i].x - 1, v[i].y)); if(v[i].y + 1 <= m) check.insert(P(v[i].x, v[i].y + 1)); } } for(int i = 0; i < 4; i++) //枚举转向灯的四个方向 { int cnt = check.size(); int x1 = v[turnid].x; int y1 = v[turnid].y; int x2 = x1 + walk[i][0]; int y2 = y1 + walk[i][1]; int x3 = x1 + walk[(i+1)%4][0]; int y3 = y1 + walk[(i+1)%4][1]; if(x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && a[x2][y2] != '.') continue; if(x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= m && a[x3][y3] != '.') continue; if(!check.count(P(x1, y1))) cnt++; if(x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !check.count(P(x2, y2))) cnt++; if(x3 >= 1 && x3 <= n && y3 >= 1 && y3 <= m && !check.count(P(x3, y3))) cnt++; if(cnt == sum) //已照亮的房间 == 需要被照亮的房间 return 1; } return 0; } int main() { //freopen("in.txt", "r", stdin); while(scanf("%d%d", &n, &m) == 2 && !(n == 0 && m == 0)) { for(int i = 1; i <= n; i++) scanf("%s", a[i]+1); int cnt = 0; //记录总共有几个格子可以放灯 for(int i = 1; i <= n; i++) //先把小于等于15个格子提出来 for(int j = 1; j <= m; j++) { if(a[i][j] == '.') { v[cnt].x = i; v[cnt].y = j; cnt++; } } if(cnt == 0) //特判 { printf("0 "); continue; } int ans = 20; for(int i = 1; i < (1 << cnt); i++) { int lcnt = 0; //记录有几个灯 int ltmp[20]; //记录灯对应的v[]的下标 for(int j = 0; j < cnt; j++) if(i & (1 << j)) ltmp[lcnt++] = j; for(int j = 0; j < lcnt; j++) if(judge(i, cnt, ltmp[j]) && lcnt < ans) ans = lcnt; } if(ans == 20) printf("-1 "); else printf("%d ", ans); } return 0; }