51. N-Queens

2019-11-06 07:34:23

字体：大中小

来源：转载

供稿：网友

题目链接： https://leetcode.com/PRoblems/n-queens/?tab=Description 这里写图片描述代码如下：

#include <iostream>#include<vector>#include<string>#include<cstdio>#include<cstring>using namespace std;#define maxn 10000vector< vector<string> > ans;int aa[maxn];int sum;void search(int cur,int n){ vector<string>aa1; if(cur==n) { for(int i=0; i<n; i++) { string tmp=""; for(int j=0; j<n; j++) { if(aa[i]==j) tmp+="Q"; else tmp+="."; } aa1.push_back(tmp); } ans.push_back(aa1); sum++;///方案加一 } else { for(int i=0; i<n; i++) { aa[cur]=i; int ok=1; for(int j=0; j<cur; j++) { if(aa[j]==aa[cur]||cur-aa[cur]==j-aa[j]||cur+aa[cur]==j+aa[j]) { ok=0; break; } } if(ok) ///代表之前的摆法是正确的，考虑下一列的摆法 search(cur+1,n); } }}int main(){ int n; while(scanf("%d",&n)==1) { sum=0;///注意初始化 ans.clear(); memset(aa,-1,sizeof(aa));///从cur=0开始 search(0,n); for(int i=0;i<ans.size();i++) { for(int j=0;j<ans[i].size();j++) { cout<<ans[i][j]<<endl; } if(i!=ans.size()-1) printf("/n/n"); } printf("%d/n",sum); } return 0;}

另：该题做法可以对比另一种解法，链接如下： http://blog.csdn.net/QQ_27690765/article/details/56669520

上一篇：golang中读写锁RWMutex和通用锁Mutex的使用

下一篇：42. Trapping Rain Water