题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1045
题目大意：
给你一幅n*n的图，再给你一些点，这些点的上下左右不能再放其他点，除非有墙（‘X’）隔着，问最多可以放多少个这样的点。
思路：
由于n不大于4，最多16个点，想到可以二进制枚举子集，然后逐个判断每个子集的可行性。
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#define FOR(i, a, b) for(int i = a; i < b; i++)
using namespace std;
int n, k;
char a[][];
int dir[][] = {,,,,-,,,-};
bool judge(int x)
{
char b[][];
int c[], tot = ;
memcpy(b, a, sizeof(a));
for(int i = ; i < n * n; i++)
{
if(x & ( << i))
{
int xx = i / n;
int yy = i % n;
if(b[xx][yy] == 'X')return false;//剪枝，如果子集覆盖了墙，直接返回假
b[xx][yy] = 'a';
c[tot++] = i;
}
}
for(int i = ; i < tot; i++)//从每个点出发
{
int x = c[i] / n;
int y = c[i] % n;
for(int i = ; i < ; i++)//四个方向遍历
{
int xx = x + dir[i][];
int yy = y + dir[i][];
while(xx >= && xx < n && yy >= && yy < n)//控制边界
{
if(b[xx][yy] == 'X')break;//碰到墙跳出循环
if(b[xx][yy] == 'a')return false;//碰到另一个'a'说明有误
xx += dir[i][];//继续往这方向遍历
yy += dir[i][];
}
}
}
return true;
}
int f(int x)//返回子集中的size
{
int tot = ;
for(int i = ; i < (n * n); i++)
{
if(x & ( << i))tot++;
}
return tot;
}
int main()
{
while(cin >> n && n)
{
int ans = ;
for(int i = ; i < n; i++)cin >> a[i];
for(int i = ; i < ( << (n * n)); i++)
{
if(judge(i))ans = max(ans, f(i));//更新最优解
}
cout << ans << endl;
}
return ;
}