文章来源地址https://www.toymoban.com/news/detail-695494.html
文章目录
- 全排列
- 八皇后
一、全排列IO链接
本题思路:本题是一道经典的全排列问题,深度优先搜索即可解决。
#include <bits/stdc++.h>
constexpr int N=10;
std::string s;
std::string ans;
int n;
bool st[N];
void dfs(int u)
{
if(u==n)
{
std::cout<<ans<<std::endl;
return;
}
for(int i=0;i<n;i++){
//如果当前字符没有遍历过,则加入到当前的字符串中去
if(!st[i]){
st[i]=true;
ans.push_back(s[i]);
dfs(u+1);//继续寻找下一个满足条件的字符
ans.pop_back();//回溯
st[i]=false;
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
std::cin>>s;
n=s.size();
dfs(0);
return 0;
}
利用STL库中的next_permutation函数来求全排列问题:
#include <iostream>
#include <algorithm>
using 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++.h>
constexpr int N=20,M=100;
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(u==8)
{
ans[++idx]=atoi(path);//加入到某一种情况中
return;
}
for(int i=0;i<8;i++){
if(!col[i]&&!dg[u+i]&&!udg[8-u+i]){
col[i]=dg[u+i]=udg[8-u+i]=true;
path[u]=i+1+'0';
dfs(u+1);
col[i]=dg[u+i]=udg[8-u+i]=false;
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);std::cout.tie(nullptr);
dfs(0);
std::cin>>n;
while(n--){
int x;
std::cin>>x;
std::cout<<ans[x]<<std::endl;
}
return 0;
}
文章来源:https://www.toymoban.com/news/detail-695494.html
到了这里,关于蓝桥杯打卡Day1的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!