http://acm.hdu.edu.cn/showproblem.php?pid=2553
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<map>
#define ms(x) memset( (x),0,sizeof(x) );
using namespace std;
typedef long long int ll;
int visited[11][11],n,ans=0;
int check(int x,int y){
for(int i=1;i<x;i++){
if(visited[i][y]==1) return 0;
}
for(int i=1;x-i>0&&y+i<=n;i++){
if(visited[x-i][y+i]==1) return 0;
}
for(int i=1;x-i>0&&y-i>0;i++){
if(visited[x-i][y-i]==1) return 0;
}
return 1;
}
void dfs(int x){
if(x==n+1){
ans++;
return ;
}
for(int i=1;i<=n;i++){
if( check(x,i) ){
visited[x][i]=1;
dfs(x+1);
visited[x][i]=0;
}
}
}
int main()
{
int key[11]={};
while(scanf("%d",&n),n){
if(key[n]){
printf("%d\n",key[n]);
continue;
}
ans=0;
ms(visited);
dfs(1);
printf("%d\n",ans);
key[n]=ans;
}
return 0;
}
ps
1.递归
2.dfs
转载请注明原文地址: https://ju.6miu.com/read-1124297.html
