HDU - 2553 - N 황후 문제

2212 단어 DFS검색 dfs
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2553
N 황후 문제
                                                Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)                                                                     Total Submission(s): 24195    Accepted Submission(s): 10767
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
 
题目分析:每一行 每一列 每一条斜线(45度)都只能放一个皇后。

注意本题需要打表,否则提交会超时。

#include
#include
using namespace std;
int sum;
int mp[100];//       ,    ,mp[]    。
bool check(int x,int y)
{
	//    x-1 。 
	for(int i=1;in)
	{
		sum++;
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(check(x,i))
		{
			mp[x]=i;//     x   i  
			dfs(x+1,n);//         
		}
	}
}
int main()
{
	int ans[11];
	for(int i=1;i<=10;i++)
	{
		sum=0;
		dfs(1,i);
		ans[i]=sum;
	}
	int n;
	while(cin>>n)
	{
		if(n==0)
		break;
		else
		cout<

좋은 웹페이지 즐겨찾기