n?n?皇后問題是指將?nn?個皇后放在?n×nn×n?的國際象棋棋盤上，使得皇后不能相互攻擊到，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。

現(xiàn)在給定整數(shù)?nn，請你輸出所有的滿足條件的棋子擺法。

輸入格式

共一行，包含整數(shù)?nn。

輸出格式

每個解決方案占?nn?行，每行輸出一個長度為?nn?的字符串，用來表示完整的棋盤狀態(tài)。

其中?.?表示某一個位置的方格狀態(tài)為空，Q?表示某一個位置的方格上擺著皇后。

每個方案輸出完成后，輸出一個空行。

注意：行末不能有多余空格。

輸出方案的順序任意，只要不重復(fù)且沒有遺漏即可。

數(shù)據(jù)范圍

1≤n≤91≤n≤9

輸入樣例：

4

輸出樣例：

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

思路

深度優(yōu)先搜索，我們需要排除永遠不可能的情況（剪枝），首先是初始化二維數(shù)組，把二維數(shù)組初始化為'.'

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';
        }
    }

深度優(yōu)先搜索分兩步走，第一步是判斷有沒有走到終點，走到終點就輸出我們需要的答案

    if(u==n)
    {
        for(int i=0;i<n;i++)    puts(g[i]);
        puts("");
        return;
    }

第二步是遍歷每一行，利用條件判斷，找到可以符合條件的情況（該題是行，對角線，反對角線不能被使用過），然后改變使用狀態(tài)，修改字符數(shù)組的內(nèi)容，遞歸調(diào)用dfs函數(shù)，恢復(fù)現(xiàn)場，把狀態(tài)和字符數(shù)組的內(nèi)容都修改回來

    int x=u;
    for(int y=0;y<n;y++)
    {
        if(!col[y]&&!dg[y+x]&&!udg[y-x+n])
        {
            col[y]=dg[y+x]=udg[y-x+n]=true;
            g[x][y]='Q';
            dfs(x+1);
            col[y]=dg[y+x]=udg[y-x+n]=false;
            g[x][y]='.';
        }
    }

這里把u和i更換成了x和y，感覺更加方便理解

代碼

#include<bits/stdc++.h>
using namespace std;

int n;
const int N=20;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)    puts(g[i]);
        puts("");
        return;
    }
    
    int x=u;
    for(int y=0;y<n;y++)
    {
        if(!col[y]&&!dg[y+x]&&!udg[y-x+n])
        {
            col[y]=dg[y+x]=udg[y-x+n]=true;
            g[x][y]='Q';
            dfs(x+1);
            col[y]=dg[y+x]=udg[y-x+n]=false;
            g[x][y]='.';
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-728167.html

?

?

到了這里，關(guān)于溫故知新：dfs模板-843. n-皇后問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！