首页 > 代码库 > HDU 2553 N皇后问题

HDU 2553 N皇后问题

2024-07-16 01:37:54   220人阅读

算法就是明白了感觉很简单，不理解就感觉那些代码是天书。

第一次接触N皇后问题是在我们的C++教材上，感觉挺困难的。我们教材上给了八皇后的代码，尼玛，就是一个八重循环。

好了，回到正题

vis数组就是保存了三个方向是否会发生冲突，如果有冲突则不再搜索。

因为我们是逐行搜索，所以不会出现一行上有两个皇后的问题。

主对角线上的规律就是，每条线上的行和列的差为定值；

副对角线是行和列的和为定值。

这样就很容易理解代码中 vis[1][col + row] 和 vis[2][n - col + row]的含义了，分别代表副对角线和主对角线

 

关于超时，由于输入数据比较多，所以打表是个不错的选择。

另外，这里有一篇很详细的文章讲用位运算来代替vis数组，马克，以后再看！

http://www.cnblogs.com/gj-Acit/archive/2013/08/04/3236148.html

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 int cnt, n, vis[3][25]; 8 int ans[12]; 9 10 void DFS(int row)11 {12     if(row == n)13     {14         ++cnt;15         return;16     }17     for(int col = 0; col < n; ++col)18     {19         if(!(vis[0][col] || vis[1][col + row] || vis[2][n - col + row]))20         {21             vis[0][col] = vis[1][col + row] = vis[2][n - col + row] = 1;22             DFS(row + 1);23             vis[0][col] = vis[1][col + row] = vis[2][n - col + row] = 0;24         }25     }26 }27 28 void Init()29 {30     for(n = 1; n <= 10; ++n)31     {32         cnt = 0;33         memset(vis, 0, sizeof(vis));34         DFS(0);35         ans[n] = cnt;36     }37 }38 39 int main(void)40 {41     #ifdef LOCAL42         freopen("2553in.txt", "r", stdin);43     #endif44 45     Init();46     int num;47     while(scanf("%d", &num) && num)48         printf("%d\n", ans[num]);49     return 0;50 }
代码君

 


联系
我们