赞
踩
N 皇后问题是指在 n x n 的棋盘上要摆 n 个皇后,
要求:任何两个皇后不同行,不同列也不在同一条斜线上,
求给一个整数n,返回 n 皇后的摆法数。
对于这个问题,因为是求最终的摆法数,也就是要遍历所有可能的状态,由此想到应该用DFS(深度优先搜索)解决
1.由于只有棋盘n行,要求每个皇后不同行,那么我们可以确定每行有且仅有一个皇后
2. 我们使用DFS依次对每行的皇后进行位置安排,即从第0行、第1行……第n-1行
3. 对于每一行,遍历所有可能的列,从而确定一个皇后的位置,并且使该列的状态被标记为已被第i行的皇后占领
4.递归调用求下一个皇后的位置
5.如果递归到n个皇后,方案数+1,然后返回
N皇后问题 #include <iostream> #include <vector> using namespace std; int ans = 0; int n; vector<int> col; bool dgcheck(int row, int co); void dfs(int k); int main() { cin >> n; col.resize(n); for (int i = 0; i < n; i++) col[i] = -1; dfs(0); cout << ans; } bool dgcheck(int row, int co)//判断当前列是否被占用以及当前位置(row,co)对角线上是否有其他皇后 { if (col[co] != -1) return false; for (int i = max(-row, -co); i + row < n && i + co < n && i + row >= 0 && i + co >= 0; i++) { if (col[co + i] == row + i) return false; } for (int i = max(-row, co - n + 1); i + row < n && co-i < n && i + row >= 0 && co-i >= 0; i++) { if (col[co - i] == row + i) return false; } return true; } void dfs(int k) { if (k == n) { ans++; return; } for (int i = 0; i < n; i++) { if (dgcheck(k, i)) { col[i] = k;//将第k个皇后放在第i列 dfs(k + 1); col[i] = -1;//将第k个皇后不放在第i列 } } }
2023.12.12更新
可以用dg和ndg数组来记录对角线上是否有皇后,关键在于给同一对角线上的元素建立唯一映射
#include<iostream> using namespace std; const int N = 20; int n; char grid[N][N]; int col[N],dg[N],ndg[N]; void dfs(int u) { if(u==n) { for(int i = 0;i<n;i++)puts(grid[i]); puts(""); } for(int i = 0;i<n;i++) { if(col[i] == 0&&dg[i-u]==0&&ndg[i+u]==0) { grid[u][i] = 'Q'; col[i]=dg[i-u]=ndg[i+u] = 1; dfs(u+1); grid[u][i] = '.'; col[i]=dg[i-u]=ndg[i+u] = 0; } } } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n; for(int i = 0;i<n;i++) { for(int j =0;j<n;j++) { grid[i][j] = '.'; } } dfs(0); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。