DFS的一道水题
题目传送门
这道题主要考察的就是回溯，搜索，标记（废话 ）
这里用四个数组来存行，列，左斜线，右斜线，不理解的话手画一个树状图也是可以的
对于左斜线上的点（i,j），由图我们可以看出，它的i+j是个定值；对于右斜线上的点，它的j-i是个定值，但有些点会存在负值，为了避免，减完以后再加个n就行了（简单处理 ）
AC Code：
#include<bits/stdc++.h>//万能头不解释
using namespace std;
int a[100],b[100],c[100],d[100];//a表示的是行；//b表示的是列；//c表示的是左斜线；//d表示的是右斜线；
int n,cnt = 0;
void dfs(int i){//深搜for (int j=1; j<=n; j++) if (b[j] == 0 && c[i+j] == 0 && d[i-j+n] == 0){//如果下一个点没有被皇后占领a[i] = b[j] = c[i+j] = d[i-j+n] = j;//标记if(i == n){//已经搜到底cnt++;//计数器加1if (cnt <= 3){//输出前三层解for (int i=1; i<=n; i++) printf("%d ",a[i]);//输出printf("\n");} } dfs(i+1);//递归a[i] = b[j] = c[i+j] = d[i-j+n] = 0;//清除标记}
}
int main(){scanf("%d",&n);dfs(1);printf("%d\n",cnt);//输出方案数return 0;//养成好习惯
}
居然跑了610ms，好快啊
溜了