hdu-2553-N皇后问题-dfs模板

描述:

在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。遇0结束。

思路:DFS。肯定一行只能有一个皇后,那就一行一行的放。

样例输入:

1
8
5
0

样例输出:

1
92
10

code:

#include<cmath>

include<cstdio>

include<cstring>

include<algorithm>

using namespace std;
const int maxn=12;
int mapmaxn;
int ans,n;
int ans_arr[maxn];
void dfs(int ithqueue);
int main()
{

for(n=1;n<maxn;++n)             //n代表几皇后 
{                
    ans=0; 
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)map[i][j]=0;            
    }
    dfs(1);                        //从第一个开始放 
    ans_arr[n]=ans;
}
int q;
while(~scanf("%d",&q),q){
    printf("%d\n",ans_arr[q]);
}
return 0;    

}
void dfs(int ithqueue){ //ithqueue代表当前放了第几个

if(ithqueue==n+1){                   //如果放到了第n+1个,代表放完了。 
    ans++;
    return ;
}
for(int col=1;col<=n;++col)                 //很明显第几个皇后代表第几行,col从1到n开始扫描,代表将当下的皇后放到第几列 
{                
    if(map[ithqueue][col]==0)                //等于0,代表可以放 
    {
        for(int i=1;i<=n;++i)                //如果该行该列该斜线还是0的话则标记 
        {            
            for(int j=1;j<=n;++j)
            {
                if(( i==ithqueue || col==j ||  abs(i-ithqueue)==abs(col-j) ) && map[i][j]==0)
                {
                    map[i][j]=ithqueue;
                } 
            }
        } 
        dfs(ithqueue+1);                    //放下一个皇后 
        
        for(int i=1;i<=n;++i)                //回溯 
        {
            for(int j=1;j<=n;++j)
            {
                if(map[i][j]==ithqueue) map[i][j]=0;
            }
        }    
    }    
}

}

Last modification:September 19th, 2019 at 06:07 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment