首页 > 代码库 > HDU 2553 N皇后问题(深搜DFS)

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

2024-07-14 03:21:54   225人阅读

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
1850
 
Sample Output
19210
 1 //经典的N皇后问题 2 #include <iostream> 3 #include <stdio.h> 4 #include <memory.h> 5 using namespace std; 6  7 int ch[25][25]; 8 int n, num, result[25]; 9 10 void dfs(int x, int y)11 {12     if(ch[x][y]) return;    //如果该点已经被攻击，则返回13     int i, xx, yy;14     if(x == n)  //如果15     {16         num++;17         return;18     }19 20     //下面个人觉得比较巧妙，因为会有重复的地方很难分析是属于哪个皇后21     //若用了下面位置的 ++ or -- ，则巧妙地避免上述情况22     //一共八个方向进行标记：上、下、左、右、左上、左下、右上、右下23     xx = x; yy = y;24     while(xx>0)  ch[xx--][y]++;25     xx = x; yy = y;26     while(yy>0)  ch[x][yy--]++;27     xx = x; yy = y;28     while(xx<=n) ch[xx++][y]++;29     xx = x; yy = y;30     while(yy<=n) ch[x][yy++]++;31     xx = x; yy = y;32     while(xx<=n && yy<=n) ch[xx++][yy++]++;33     xx = x; yy = y;34     while(xx>0  && yy<=n) ch[xx--][yy++]++;35     xx = x; yy = y;36     while(xx<=n && yy>0)  ch[xx++][yy--]++;37     xx = x; yy = y;38     while(xx>0  && yy>0)  ch[xx--][yy--]++;39 40     for(i = 1; i <= n; i++)41     {42         dfs(x+1, i);43     }44 45     //若这个皇后深搜后的结果不成功，则要返回原来的情况，八个方向都 --46     xx = x; yy = y;47     while(xx>0)  ch[xx--][y]--;48     xx = x; yy = y;49     while(yy>0)  ch[x][yy--]--;50     xx = x; yy = y;51     while(xx<=n) ch[xx++][y]--;52     xx = x; yy = y;53     while(yy<=n) ch[x][yy++]--;54     xx = x; yy = y;55     while(xx<=n && yy<=n) ch[xx++][yy++]--;56     xx = x; yy = y;57     while(xx>0  && yy<=n) ch[xx--][yy++]--;58     xx = x; yy = y;59     while(xx<=n && yy>0)  ch[xx++][yy--]--;60     xx = x; yy = y;61     while(xx>0  && yy>0)  ch[xx--][yy--]--;62 }63 64 void init()     //初始化函数65 {66     int i, j;67     for(i = 0; i < 12; i++)68         for(j = 0; j < 12; j++)69             ch[i][j] = 0;70 }71 72 void set()73 {74     int i, k;75     for(k = 1; k <= 10; k++)76     {77         num = 0; n = k;     //初始化78         for(i = 1; i <= k; i++)79         {80             init();         //初始化81             dfs(1, i);      //继续dfs寻找82         }83         result[k] = num;84     }85 }86 87 int main()88 {89     set();90     while(scanf("%d", &n), n)91     {92         printf("%d\n", result[n]);93     }94 95     return 0;96 }
View Code

 


联系
我们