843. n-皇后问题

题目：

这道题呢唯一一点与其他题目不同之处就是它有有 3 个 v i s 数组

以及是一行一行深搜的。

主要思路为：

从第一行到第n行，一行放一个，这一行从第一列到第n列遍历，同时满足下列条件即可放置皇后

1.这一列没放

2.这一位置的对角线没放

3.这一位置的反对角线没放

程序实现：

深搜的u参数表示行数，dfs中的i表示列数，col[i] 表示i列的状态1表示已放过了0表示没放过，dg[u+i]表示u 行 i列的斜线的状态1表示已放过了0表示没放过，udg[n-u+i] 表示u行i列的反斜线的状态1表示已放过了0表示没放过。

程序：

#include<bits/stdc++.h>

using namespace std;

const int N=20;

int n,dg[N],udg[N],col[N];

char g[N][N];

void dfs(int u)

{

    if(u==n)

    {

        for(int i=0;i<n;i++)

        {

            for(int j=0;j<n;j++)

            {

                cout<<g[i][j];

            }

            cout<<endl;

        }

        puts("");

        return;

    }

    else

    {

        for(int i=0;i<n;i++)

        {

            if(dg[u+i]==0&&udg[n-u+i]==0&&col[i]==0)

            {

                g[u][i]='Q';

                dg[u+i]=1;

                udg[n-u+i]=1;

                col[i]=1;

                dfs(u+1);

                dg[u+i]=0;

                udg[n-u+i]=0;

                col[i]=0;

                g[u][i]='.';

            }

        }

    }

}

int main()

{

    cin>>n;

    memset(g,'.',sizeof(g));

    dfs(0);

    return 0;

}

巴特西

843. n-皇后问题

最新文章

热门文章