P1562 还是 N 皇后网页链接P1562 还是 N 皇后题目背景正如题目所说这题是著名的N NN皇后问题。题目描述一个 $ N×N $ 的跳棋棋盘有 $ N $ 个皇后棋子被放置在棋盘上使得每行、每列有且只有一个皇后棋子每条对角线包括两条主对角线的所有平行线上至多有一个皇后棋子。棋盘上一部分格子可以放置棋子而另一部分则不可以。求放置棋子的方案总数。输入格式第一行有一个N NN。接下来有N NN行N NN列描述一个棋盘*表示可放.表示不可放。输出格式输出方案总数。输入输出样例 #1输入 #14 **.* **** **** ****输出 #11说明/提示0 n ≤ 14 0 n\le140n≤14解题思路本题是带障碍的 N 皇后计数问题。在标准 N 皇后基础上某些格子禁止放置。使用位运算优化的回溯算法Bitmask DFS利用整数的二进制位表示当前行可放置皇后的位置通过位运算快速排除列与两条对角线上的攻击冲突并跳过障碍格大幅提高搜索效率。1. 问题等价转化N 皇后规则在N × N N \times NN×N棋盘放置N NN个皇后使得它们互不攻击。即每行、每列、每条对角线至多一个皇后。障碍限制某些格子标为.表示不可放。在逐行放置时将当前行的障碍格预先从候选位置中排除。状态表示对于当前行已放置皇后会攻击到的位置可由三个整数表示u1列冲突第i ii位为1 11表示第i ii列已被占据。u2左斜对角线冲突行列固定放置后向下一行传递时需左移一位1。u3右斜对角线冲突行-列固定放置后向下一行传递时需右移一位1。合法候选位当前行可放置的位为~ (u1 | u2 | u3 | f[row])再与全N NN位的掩码(1n)-1取与。其中f[row]为预处理的当前行障碍掩码障碍位为1 11。2. 算法实现位运算 DFS障碍预处理读取棋盘将每行的障碍位置转换为一个N NN位二进制数f[i]障碍位设为1 11。DFS 递归函数dfs(u1, u2, u3, row)若u1 (1n)-1即所有列均已放置填满N NN个皇后方案数ans返回。计算当前行合法位置p all ~(u1 | u2 | u3 | f[row])。循环取出每个合法位置通过lowbit依次摘除最低位的1 11设选中的位为bit。递归到下一行dfs(u1|bit, (u2|bit)1, (u3|bit)1, row1)。lowbit宏#define lowbit(x) ((x)(-x))用于快速获取二进制数中最低位的1 11。主函数读入N NN和棋盘初始化障碍掩码调用dfs(0,0,0,1)输出ans。3. 复杂度分析时间复杂度标准 N 皇后时间复杂度为O ( N ! ) O(N!)O(N!)位运算极大剪枝后实际运行极快N ≤ 14 N \le 14N≤14瞬间完成。空间复杂度递归栈深度O ( N ) O(N)O(N)掩码数组O ( N ) O(N)O(N)极小。总结使用三个整数分别维护列、左对角线、右对角线的攻击覆盖结合预处理的障碍掩码通过位运算快速生成合法候选位置并递归搜索。回溯过程自然实现了逐行放置、全局计数的功能简洁且高效。代码简要说明全局变量n棋盘大小ans方案数f[30]记录每行障碍掩码。障碍读取将每行字符串转换为二进制障碍格对应位置1 11存入f[row]。DFS 函数参数u1, u2, u3分别为列、左对角线、右对角线的禁止位掩码o为当前行号。若u1全1 11则计数返回。p 全1掩码 (~(u1|u2|u3|f[o]))得到可放位置。循环摘取p中的1 11递归进入下一行。主函数读入数据调用dfs(0,0,0,1)输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;#definelowbit(x)((x)(-x))ll n,ans,f[30];voiddfs(ll u1,ll u2,ll u3,ll o){if(u1(1LLn)-1){ans;return;}ll p((1LLn)-1)(~(u1|u2|u3|f[o]));while(p){dfs(u1lowbit(p),(u2lowbit(p))1,(u3lowbit(p))1,o1);p-lowbit(p);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){string s;cins;for(ll p0;pn;p)if(s[p].)f[i]|(1LL(n-p-1));}dfs(0,0,0,1);coutansendl;return0;}
)
