HDU 2553 N 황후 문제 (역시 DFS)


N 황후 문제
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15744    Accepted Submission(s): 7157
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 
원본 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2553
사고방식: 아니면 황후 가 같은 열 에 있 는 지, 같은 주 대각선 에 있 는 지, 같은 대각선 에 있 는 지 를 검색 하고 판단 하 는 것 이 관건 입 니 다. 누 군 가 는 2 차원 수조 로 각각 표 시 를 하고 수학 관계 로 판단 하 는 사람 도 있 습 니 다.
AC 코드:

#include<stdio.h>
#include<string.h>
#define MAX 100
int visit[3][MAX];
int ans[MAX];
int sum,n;
void dfs(int num)//num        
{
    int i,j;
    if(num==n+1)
    {
        sum++;
        return;
    }
    for(i=1; i<=n; i++) //     
    {
        if(!visit[0][i]&&!visit[1][num+i]&&!visit[2][num-i])//                  
        {
            visit[0][i]=visit[1][num+i]=visit[2][num-i]=1;
            dfs(num+1);
            visit[0][i]=visit[1][num+i]=visit[2][num-i]=0;
        }
    }
}
int main()
{
    int i,j;
    memset(ans,0,sizeof(ans));
    for(i=1; i<=10; i++)
    {
        sum=0;
        memset(visit,0,sizeof(visit));
        n=i;
        dfs(1);
        ans[i]=sum;
    }
    while(scanf("%d",&n),n)
    {
        printf("%d
",ans[n]);
    }
    return 0;
}

AC 코드 2:

#include<stdio.h>//     
#include<math.h>
int x[15],y[15]= {0};
int sum,n;
int place(int k)
{
    int i;
    for(i=1; i<k; i++)
    {
        if(abs(k-i)==abs(x[k]-x[i])||x[k]==x[i])
            //  ，           ,i         ，x[i]       ，
            //                       ,             。
            //       ，       i       
            return 0;
    }
    return 1;
}
void DFS(int a)
{
    int i;
    if(a>n)
    {
        sum++;
        return;
    }
    for(i=1; i<=n; i++)
    {
        x[a]=i;// a       
        if(place(a))//        
            DFS(a+1);//             
    }
}
int main()
{
    int i,j,n1;
    for(i=1; i<=10; i++)
    {
        n=i;//      
        sum=0;//       0
        DFS(1);//           
        y[i]=sum;
    }
    while(scanf("%d",&n1)==1&&n1)
    {
        printf("%d
",y[n1]);
    }
    return 0;
}