DFS 经典题

第一种搜索顺序

/*n皇后问题，第一种搜索顺序*/
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=10;

int n;
bool row[N],col[N],dg[N*2],udg[N*2];
char g[N][N];

void dfs(int x,int y,int s)
{
    if(s>n)return;//n个点枚举完成 
    if(y==n)y=0,x++;//第x行枚举完了，移动到下一行 

    if(x==n)
    {//枚举到了最后一行 
        if(s==n)
        {//输出符合条件的棋盘 
            for(int i=0;i<n;i++)puts(g[i]);
            puts(""); 
        } 
        return;
    } 

    g[x][y]='.';
    dfs(x,y+1,s);

    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])//只需保证不同对角线对应不同数组下标就行！
    {
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=true;
        g[x][y]='Q';
        dfs(x,y+1,s+1);
        g[x][y]='.';
        row[x]=col[y]=dg[x+y]=udg[x-y+n]=false;
    } 
} 
int main()
{
    cin>>n;
    dfs(0,0,0);
    return 0;
}

第二种搜索方式，一行一行地枚举，更快！

#include<iostream>

using namespace std;

const int N=10;

bool col[N],dg[N*2],udg[N*2];
char g[N][N];
int n;

void dfs(int u)
{
    if(u==n){
        for(int i=0;i<n;i++)puts(g[i]);
        puts("");
        return;
    }
    for(int i=0;i<n;i++){
        //每一层u代表行，i代表枚举该列的所有位置
        if(!col[i]&&!dg[i+u]&&!udg[u-i+n])
        {
            col[i]=dg[i+u]=udg[u-i+n]=true;
            g[u][i]='Q';
            dfs(u+1);
            col[i]=dg[i+u]=udg[u-i+n]=false;
            g[u][i]='.';
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    return 0;
}