HDU2553 N皇后问题

2024-08-26 08:32

文章标签 问题皇后 hdu2553

本文主要是介绍HDU2553 N皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大致题意：在N*N的棋盘上摆放N个皇后，注意是正好N个皇后二不是小于N，使横竖左右均没有对应的皇后，完成一次求解。统计这样的次数。
大致思路：如果做过Fire Net （http://acm.hdu.edu.cn/showproblem.php?pid=1045）的话会很自然想到建立一个10 * 10 的二维数组来保存这样的棋盘，每次放置一个棋子并且判断是否可以放置，如果可以放置则进行下一次的搜索。大致代码会如下：

DFS(int pos)
{if (pos == N * N)total++;return;x = pos / N;y = pos % N;if (can_put(x, y))put_chess(x, y);DFS(pos + 1);remove_chess(x, y);
}

上述代码有很多地方可以优化，比如搜索下一个位置就不必再搜索与这个同行的，从而减少很多无用的判断。
而书上给出的算法则没有在一个二维数组中，利用了每行只能摆放一个皇后的性质，只用了一个一维数组用来存储第 i 行中棋子的位置C[i]。

#define MAXN    11
// 使用全局变量减少函数参数数量的增加
int C[MAXN], N, total;void DFS(int deep) 
{if (deep == N)  total++;else for (int i = 0; i < N; ++i) {// 先装模作样的把皇后放在(deep, i)上面，检测是否符合要求，即不冲突C[deep] = i;//bool ok = true;for (int j = 0; j < deep; ++j) {if (C[deep]==C[j]||deep-j==C[deep]-C[j]||deep-j==C[j]- C[deep]){ok = false;break;}}if (ok) DFS(deep + 1);}
}
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifstd::ios::sync_with_stdio(false);int ns[15];for (N = 1; N <= 10; ++N){total = 0;DFS(0);ns[N] = total;}while (cin >> N && N) {cout << ns[N] << endl;}return 0;
}

其中判断是否在同一列以及斜线上的条件令我思考了一会，利用了斜率为1和-1的原理，即y1 - y2 == x1 - x2和y1 - y2 == x2 - x1折两个条件判断斜线。另外最开始的代码提交后TLE了，想了想不是C++ cin和cout的问题。我继续搜索题解发现可以先用数组保存结果（因为结果仅仅有10个，从1到10），想想就应该明白测试文件里面会有很多的重复（开始我以为也就是从1测试到10 结束），保存下来应答就不用每次都计算而节省了大量时间。

==================更新=================
另外刘汝佳的书上还介绍了另外一种继续提高效率的做法，使用一个二维数组vis 标记是否被放置过皇后，直接使用一个for循环来判断，代码如下：

void search(int cur)
{if (cur == n)   tot++;else for (int i = 0; i < n; ++i) {if (!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n]) {C[cur] = i;vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;search(cur + 1);vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;}}
}