九度oj 题目1254：N皇后问题

题目描述：

N皇后问题，即在N*N的方格棋盘内放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在同一斜线上。因为皇后可以直走，横走和斜走如下图)。

你的任务是，对于给定的N，求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。

输入：: 输入包含多组测试数据。
每组测试数据输入一个整数n(3<n<=13),表示有n*n的棋盘，总共摆放n个皇后。

输出：: 对于每组测试数据，输出总共不同的摆放情况个数，结果单独一行。

样例输入：

样例输出：

2

开始的代码如下

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <cmath>

 int cnt[];

 int ans[];

 int pan(int row, int col) {

     int panA = col - row;

     int panB = col + row;

     for(int i = ; i < row; i++) {

         if(ans[i] - i == panA || ans[i] + i == panB || ans[i] == col) {

             return false;

         }

     }

     return true;

 }

 void dfs(int row, int n) {

     if(row == n) {

         cnt[n]++;

         return;

     }

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

         if(pan(row, i)) {

             ans[row] = i;

             dfs(row+, n);

         }

     }

 }

 int main(int argc, char const *argv[])

 {

     int n;

     while(scanf("%d",&n) != EOF){

         memset(cnt, , sizeof(cnt));

         dfs(, n);

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

     }

     return ;

 }

用一个一维数组存储放置的状态，用回溯法求解，但这样做还是太慢，提交时采用暴力的办法

 #include <cstdio>

 int cnt[]= {,,,,,,,,,,,,,};

 int main(int argc, char const *argv[])

 {

         int n;

     while(scanf("%d",&n) != EOF){

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

     }

     return ;

 }

参考别人博客，用位运算来求解是最快的办法

参考：http://blog.csdn.net/hackbuteer1/article/details/6657109

巴特西

九度oj 题目1254：N皇后问题

最新文章

热门文章