HDU 2553 N 황후 문제 (DFS 역 추적)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 17312 Accepted Submission(s): 7859
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
Author
cgf
Source
2008 HZNU Programming Contest
Recommend
lcy | We have carefully selected several similar problems for you: 2614 1258 1045 1426 1035
문제 풀이: 타 표 (1 ~ 10) + 역 추적 dfs...
AC 코드:
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;
int x[15],num[15]={0};
int sum;
int n;
int check (int k)
{
for(int i=1;i<k;i++)
{
// ， ,i ，x[i] ，
// , 。
// ， i
if(abs(k-i)==abs(x[k]-x[i])||x[k]==x[i])
return 0;
}
return 1;
}
void dfs(int a)
{
if(a>n)
{
sum++;
}
else for(int i=1;i<=n;i++)
{
x[a]=i; // a i
if(check(a))
{
dfs(a+1);
}
}
}
int main()
{
int N;
for(int i=0;i<=10;i++)
{
n=i; //
sum=0; //
dfs(1); //
num[i]=sum; //
}
while(~scanf("%d",&N)&&N)
{
printf("%d
",num[N]);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
