题解 P1219 【八皇后】

# 八皇后 ## 1.简介 如题所示，这是一个类似于**枚举**的过程：每一行每一行地进行尝试，如果没有皇后能侵犯到自己， 就**放置**该棋子，同时占据她所能**占据**的所有领地。最后，在每一行上都各有一个皇后时，就输出答案 ## 2.方法 在这道题中，主要使用的是**深搜(DFS)**和**回溯** 回溯：借用以下**神子杏**大佬的批批替 为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是**错误**的，就退回上一步重新选择条件，继续向前探索，如此反复进行，直至得到解或证明无解。 Ta的特点如下： 1.可以在借助系统栈储存状态 2.空间为O(深度) 3.可以剪枝 4.比较容易实现 5.不易判重 这个就是我们在这道题中的主要思路。如果在准备放置皇后的时候发现，这一行都没有合适的位置，那么我们就“报错”：退回**上一状态**，重新来过。 为了让皇后们可以吃“后悔药”，我们就必须给她们留下后路——曾经打过标记的地方都**撤销**掉，让她们有路可回。 下面，说下具体的实现方法。 ## **1.地图设置** 在这道题当中，我们不采取一般的建图（姑且先用下这个词）方式——建一个**二维数组**。因为这样的话，我们需要更多的循环来支持**占领**操作。 ### 我们分别为**行**、**列**、**左斜线（/)**、**右斜线(\ )** 单独建立数组。 #### 这样做的好处非常明显：在进行占据操作的时候，只需要在相对应的行、列、左斜、右斜打上标记就行，不需要在每一块都用循环进行操作，节省很多时间 类似这种建图方式的题还有[这道](https://www.luogu.org/problem/P1784)，自己尝试一下吧！ 行和列的表示都非常简单，只需要在对应格子标记即可，我们来看一下左斜右斜的表示方式 如图：  对于第二行的那个皇后来说，她的右斜线上的点，（1，3），（3，5），（4，6），我们可以看出，它的$y-x$是个定值2，但是看第四行的皇后的右斜线上的点（5，2），它的$y-x$是个负定值，而数组是不能存在负数下标的，那怎么办。 ### 把数组向右平移几个单位(在这里平移$n$就够) 因为右斜线上所有数都向右平移了$n$，所以总的数组中的关系不变。 同理我们看左斜线上的点，我们发现它们的$x+y$是个定值（自己找找看） 因为这是个加法，不会出现负数的情况，所以我们不需要在末尾加上$n$ 所以，我们在写的时候可以这样 ``` ls[i+j]=1;rs[i-j+n]=1 ``` 以上就是些基本操作，下面加入代码（我的代码里的左斜和右斜好像写反了） ```cpp #include<bits/stdc++.h> using namespace std; int n,ans=0; int a[105],ls[105],rs[105],kkk[105];//a:lie,ls:left scope,rs:right scope（原谅我的工地英语），kkk是行（kkksc03不要打我[滑稽]） void print() { if(ans<=2) { for(int i=1;i<=n;i++) cout<<kkk[i]<<" "; cout<<endl; }//输出前三组解 ans++; } void dfs(int k)//深搜 { if(k>n) { print(); return ; } for(int i=1;i<=n;i++) { if(!a[i]&&!ls[i+k]&&!rs[i-k+n]) { kkk[k]=i; a[i]=1; ls[k+i]=1; rs[i-k+n]=1;//以上是“占领”操作 dfs(k+1);//这个是深搜下一行 a[i]=0;//以下是回溯操作 ls[k+i]=0; rs[i-k+n]=0; } } } int main () { cin>>n; dfs(1);//开始 cout<<ans<<endl;//结束 return 0;//大工告成！ } ```