2020-07-29

1.題目描述

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

2.題解

回溯算法

3.代碼

class Solution { public:vector<vector<string>> solveNQueens(int n) {if (n==0) return vector<vector<string>>(0);vector<bool> colum(n,false);vector<bool> f1(2*n,false); // 主對角線vector<bool> f2(2*n,false); // 副對角線string s;for (int i=0;i<n;i++) s.push_back('.');vector<string> vec;for (int i=0;i<n;i++){vec.push_back(s);}dfs(0,n,vec,colum,f1,f2);return res;}bool isvalid(int x,int y,int n,vector<bool> colum,vector<bool> f1,vector<bool> f2){if (colum[y]||f1[x-y+n-1]||f2[x+y]) return false;return true;}void dfs(int x,int n,vector<string> vec,vector<bool> colum,vector<bool> f1,vector<bool> f2){if (x==n){res.push_back(vec);return ;}for (int y=0;y<n;y++){if (isvalid(x,y,n,colum,f1,f2)){colum[y]=true;f1[x-y+n-1]=true;f2[x+y]=true;vec[x][y]='Q';dfs(x+1,n,vec,colum,f1,f2);colum[y]=false;f1[x-y+n-1]=false;f2[x+y]=false;vec[x][y]='.';}}}vector<vector<string>> res; }; class Solution { public:int totalNQueens(int n) {if (n==0) return 0;vector<bool> colum(n,false);vector<bool> f1(2*n,false); // 主對角線vector<bool> f2(2*n,false); // 副對角線res=0;dfs(0,n,colum,f1,f2);return res;}bool isvalid(int x,int y,int n,vector<bool> colum,vector<bool> f1,vector<bool> f2){if (colum[y]||f1[x-y+n-1]||f2[x+y]) return false;return true;}void dfs(int x,int n,vector<bool> colum,vector<bool> f1,vector<bool> f2){if (x==n){res++;return ;}for (int y=0;y<n;y++){if (isvalid(x,y,n,colum,f1,f2)){colum[y]=true;f1[x-y+n-1]=true;f2[x+y]=true;dfs(x+1,n,colum,f1,f2);colum[y]=false;f1[x-y+n-1]=false;f2[x+y]=false;}}}int res; };

總結

以上是生活随笔為你收集整理的51. N皇后/52. N皇后 II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。