知识点：深搜，剪枝，位运算

难度：3

感觉这个题还是比别的难度为3的题要难一些，因为用到了状压搜索，我这里使用的写法是把每一行的状态当成了函数参数的写法，也就是函数里面有三个参数表示状态，每个数表示当前行的每一列当前情况下是不是可选的点，第一个是竖直，第二个是右上到左下的对角线，第三个是左上到右下的对角线，然后我们向下一层递归的时候要计算出新的参数，两个对角线分别需要用到移位运算，然后高位低位分别补1，

我这个时间效率还不是很高，1.8s，我看洛谷其它的提交基本上都是1s左右，甚至还有500ms的，说明我这个还有将近一倍的优化空间，而且我这个不能放置的点是在递归函数里面判断的，不是一开始就预处理好的

#include using namespace std;const int N = 14;int n, ans, h[1 << N];
string s[N];int lowbit(int x) {return x & -x;
}void dfs(int k, int col, int dia1, int dia2) {if (k == n) {ans++;return;}int num = col & dia1 & dia2;for (int i = num; i; i -= lowbit(i)) {int t = lowbit(i);if (s[k][h[t]] == '.') continue;col -= t;int t1 = dia1, t2 = dia2;dia1 = ((dia1 - t) >> 1) + (1 << (n - 1));dia2 = ((dia2 - t) << 1) + 1;dia2 &= (~(1 << n));dfs(k + 1, col, dia1, dia2);col += t;dia1 = t1; dia2 = t2;}
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> s[i];h[1 << i] = i;}int init = (1 << n) - 1;dfs(0, init, init, init);cout << ans;return 0;
}