HDU 2553 N皇后问题(深搜DFS)

时间：2023-01-23 16:40:44

N皇后问题

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1757    Accepted Submission(s): 772


 

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
 //经典的N皇后问题

 #include <iostream>

 #include <stdio.h>

 #include <memory.h>

 using namespace std;

 int ch[][];

 int n, num, result[];

 void dfs(int x, int y)

 {

     if(ch[x][y]) return;    //如果该点已经被攻击，则返回

     int i, xx, yy;

     if(x == n)  //如果

     {

         num++;

         return;

     }

     //下面个人觉得比较巧妙，因为会有重复的地方很难分析是属于哪个皇后

     //若用了下面位置的 ++ or -- ，则巧妙地避免上述情况

     //一共八个方向进行标记：上、下、左、右、左上、左下、右上、右下

     xx = x; yy = y;

     while(xx>)  ch[xx--][y]++;

     xx = x; yy = y;

     while(yy>)  ch[x][yy--]++;

     xx = x; yy = y;

     while(xx<=n) ch[xx++][y]++;

     xx = x; yy = y;

     while(yy<=n) ch[x][yy++]++;

     xx = x; yy = y;

     while(xx<=n && yy<=n) ch[xx++][yy++]++;

     xx = x; yy = y;

     while(xx>  && yy<=n) ch[xx--][yy++]++;

     xx = x; yy = y;

     while(xx<=n && yy>)  ch[xx++][yy--]++;

     xx = x; yy = y;

     while(xx>  && yy>)  ch[xx--][yy--]++;

     for(i = ; i <= n; i++)

     {

         dfs(x+, i);

     }

     //若这个皇后深搜后的结果不成功，则要返回原来的情况，八个方向都 --

     xx = x; yy = y;

     while(xx>)  ch[xx--][y]--;

     xx = x; yy = y;

     while(yy>)  ch[x][yy--]--;

     xx = x; yy = y;

     while(xx<=n) ch[xx++][y]--;

     xx = x; yy = y;

     while(yy<=n) ch[x][yy++]--;

     xx = x; yy = y;

     while(xx<=n && yy<=n) ch[xx++][yy++]--;

     xx = x; yy = y;

     while(xx>  && yy<=n) ch[xx--][yy++]--;

     xx = x; yy = y;

     while(xx<=n && yy>)  ch[xx++][yy--]--;

     xx = x; yy = y;

     while(xx>  && yy>)  ch[xx--][yy--]--;

 }

 void init()     //初始化函数

 {

     int i, j;

     for(i = ; i < ; i++)

         for(j = ; j < ; j++)

             ch[i][j] = ;

 }

 void set()

 {

     int i, k;

     for(k = ; k <= ; k++)

     {

         num = ; n = k;     //初始化

         for(i = ; i <= k; i++)

         {

             init();         //初始化

             dfs(, i);      //继续dfs寻找

         }

         result[k] = num;

     }

 }

 int main()

 {

     set();

     while(scanf("%d", &n), n)

     {

         printf("%d\n", result[n]);

     }

     return ;

 }

相关文章