P1219 [USACO1.5] 八皇后 Checker Challenge题目描述一个如下的6×66 \times 66×6的跳棋棋盘有六个棋子被放置在棋盘上使得每行、每列有且只有一个每条对角线包括两条主对角线的所有平行线上至多有一个棋子。上面的布局可以用序列2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5246135来描述第iii个数字表示在第iii行的相应位置有一个棋子如下行号1 2 3 4 5 61\ 2\ 3\ 4\ 5\ 6123456列号2 4 6 1 3 52\ 4\ 6\ 1\ 3\ 5246135这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。并把它们以上面的序列方法输出解按字典顺序排列。请输出前333个解。最后一行是解的总个数。输入格式一行一个正整数nnn表示棋盘是n×nn \times nn×n大小的。输出格式前三行为前三个解每个解的两个数字之间用一个空格隔开。第四行只有一个数字表示解的总数。解题思路很典型的深搜主要问题放在怎么去处理行列对角线的关系上面。其实这里的dfs不必给出两个参数x,y只用一个量表示行数就可以。设a,b,c,d四个数组分别记录行列左对角右对角的是否存在省去了循环的繁琐判断。除此以外对前3个解的输出其实也没有必要进行储存直接输入避免二维的繁琐。完整代码如下#includebits/stdc.husingnamespacestd;inta[30],n,ans0;boolb[30],c[30],d[30];voiddfs(intx){if(xn){//这里超级重要//循环的终止条件一定是xn而不是xn因为会出现无效解的情况//没有判断xn是否存在有效解ans;if(ans3){for(inti1;in;i)printf(%d ,a[i]);putchar(\n);}return;}for(inti1;in;i){if(!b[i]!d[ix]!c[i-xn]){a[x]i,b[i]1,d[ix]1,c[i-xn]1;dfs(x1);b[i]0,d[ix]0,c[i-xn]0;}}}intmain(){cinn;dfs(1);coutans;return0;}到此AC(´ω)