洛谷P1219 N皇后问题题解

这是一道很好的DFS模版题，很适合新手拿来理解dfs.

题目描述

有一个N*N的棋盘，要在上面放N个棋子，使每个棋子的行、列、对角线上都没有其他棋子，
要求输出前三种情况的序列（a[i]=j表示在i行j列有一个棋子），最后输出总的情况数。
数据范围：6<=n<=13

思路拆分

由于我们不知道棋子具体可以放在哪些位置，但可以确定的是肯定都不在一列（或一行）上，所以我们可以用循环遍历列（或行），用深搜枚举每一个位置。

完整代码

#include<bits/stdc++.h>usingnamespacestd;intn;intcnt;inta[15];boolc[16],d1[30],d2[30];//当前行、当前主对角线（左下到右上）、当前副对角线是否合法boolcheck(intr,inti){return!c[i]&&!d1[r-i+n]&&!d2[i+r];//检查当前位置是否合法}voiddfs(intr){if(r==n){cnt++;if(cnt<=3){for(inti=0;i<n;i++){cout<<a[i]+1<<" ";}cout<<endl;}return;}for(inti=0;i<n;i++)//遍历每一行{if(check(r,i))//检查{//放a[r]=i;c[i]=d1[r-i+n]=d2[i+r]=true;dfs(r+1);//回溯c[i]=d1[r-i+n]=d2[i+r]=false;}}}intmain(){cin>>n;dfs(0);cout<<cnt;return0;}