合肥专业建站,整合营销案例分析,个人网页设计要素,惠州市建设规划局网站文章目录
全排列八皇后 一、全排列IO链接
本题思路:本题是一道经典的全排列问题#xff0c;深度优先搜索即可解决。
#include bits/stdc.hconstexpr int N10;std::string s;
std::string ans;
int n;
bool st[N];void dfs(int u)
{if(un){std::coutans… 文章目录
全排列八皇后 一、全排列IO链接
本题思路:本题是一道经典的全排列问题深度优先搜索即可解决。
#include bits/stdc.hconstexpr int N10;std::string s;
std::string ans;
int n;
bool st[N];void dfs(int u)
{if(un){std::coutansstd::endl;return;}for(int i0;in;i){//如果当前字符没有遍历过,则加入到当前的字符串中去if(!st[i]){st[i]true;ans.push_back(s[i]);dfs(u1);//继续寻找下一个满足条件的字符ans.pop_back();//回溯st[i]false;}}
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cins;ns.size();dfs(0);return 0;
}
利用STL库中的next_permutation函数来求全排列问题
#include iostream
#include algorithmusing namespace std;int main()
{string s;cin s;do cout s \n;while(next_permutation(s.begin(), s.end()));return 0;
}
二、八皇后IO链接
本题思路:利用dfs的方式找出92组解判定该点是否可以放皇后时用了三个bool类型的数组col[N], dg[N], udg[N]来储存某列某正对角线某副对角线是否可以放置所以当其中值为true时就不能在该点放。我们需要一个数组ans来储存答案同时我们得想办法把每个皇后所在列转成int类型存起来。为了方便我们在进行dfs时可以先把答案用char类型储存在path[8]数组里面最后转成int类型放进ans数组最后处理m次询问就行。
#include bits/stdc.hconstexpr int N20,M100;int n,ans[M];//ans保存92种八皇后信息
int idx;
char path[8];
bool col[N],dg[N],udg[N];//col表示列,dg表示主对角线,udg表示副对角线void dfs(int u)
{if(u8){ans[idx]atoi(path);//加入到某一种情况中return;}for(int i0;i8;i){if(!col[i]!dg[ui]!udg[8-ui]){col[i]dg[ui]udg[8-ui]true;path[u]i10;dfs(u1);col[i]dg[ui]udg[8-ui]false;}}
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);dfs(0);std::cinn;while(n--){int x;std::cinx;std::coutans[x]std::endl;}return 0;
}
