P1219 [USACO1.5] 八皇后 Checker Challenge题解

· · 题解

这题我本来是不想写题解的，但由于这题很经典且我做了3遍都能不理解，我为我自己大家写下了这篇回忆录题解。

回归主题

妥妥又经典的 dfs 题这是一句病句别学我，从1枚举棋子列数，记录下棋子所在列，两个对角线，下一次如果行与两个斜对角没有可以攻击到这个点的棋子，那么就把棋子放进去。

思路已经明确。那么怎么记录下棋子所在的列与对角线捏(本人第二次就栽在这)？

列：

我们可以开个循环，直接记录循环到了哪一列（so easy)。

对角线：

列非常容易记录，但对角线就麻烦了，这里引用一张别人的图片。 我们可以很清楚滴看到，当 i+j 的时候（i是左边的数字，j是上面的字母，实际也是 1 到 9，由于是引用，没有办法改 QwQ,请见谅），由下往上的对角线所代表的数是一样的， i-j 时，由上往下的对角线所代表的数字相同，以为i-j有可能导致负数，而数组是不可以像 a[-1] 这样的开的，所以，代码里我是用 i-j+15 来记录的。

然鹅，本人第三次还是不会

当我查看我之前的代码时（代码详见下面的 ac code）， a[x]=i 困住了我的大脑。what,最初 x 和 i 不是 1 吗？这开头不得输出 1?

很明显，这个人没学好回溯。。。

如果你的回溯很ok就可以跳过这里啦。

当 a[1]=1 时,这种情况不可能形成题目要求的状况（不用问为什么），这时候，深搜无法进行下去，就会回来，而我们便将一开始的标记收回，去寻找下一个答案。如果深搜结束了，标记也会收回，来寻找新的答案。

这样，代码就大功告成了。

ac code:

#include<bits/stdc++.h>
using namespace std;
int sum,n,a[20],d1[20],d2[80],d3[80];//d1记录列，d2和d3记录对角线 
void dfs(int x){
    if(x>n){//如果已经放入n个棋子 
        sum++;//放置总数+1 
        if(sum<=3){//如果是前三个 
            for(int i=1;i<=n;i++)//输出 
                cout<<a[i]<<' ';
            cout<<endl;
        }
    }
    for(int i=1;i<=n;i++){
        if(d1[i]==0&&d2[i+x]==0&&d3[x-i+15]==0){//没有棋子可以攻击到这里 
            a[x]=i;//记录x行的棋子在i列 
            d1[i]=1;d2[i+x]=1;d3[x-i+15]=1;//标记 
            dfs(x+1);
            d1[i]=0;d2[i+x]=0;d3[x-i+15]=0;//回溯 
        }
    }
}
int main(){
    cin>>n;
    dfs(1);
    cout<<sum;
    return 0;
}

希望大家喜欢反正我喜欢 QwQ。