算法基础课复习第三天<DFS>
作者:
骏杰
,
2022-04-30 21:55:46
,
所有人可见
,
阅读 136
排列数字:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=10;
bool st[N];
int path[N];
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) cout<<path[i]<<" ";
cout<<endl;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
n皇后:
第一种方法:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=20;
char g[N][N];
bool col[N];//列
bool dg[N],udg[N];//正反对角线
int n;
void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++) cout<<g[i]<<endl;
cout<<endl;
return ;
}
for(int i=0;i<n;i++)
{
if(!col[i]&&!dg[u+i]&&!udg[n-u+i])//y=x+b y=-x+b
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i]=dg[u+i]=udg[n-u+i]=false;
g[u][i]='.';
}
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
g[i][j]='.';
}
}
dfs(0);
return 0;
}
第二中方法:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=20;
char g[N][N];
bool row[N],col[N];//列
bool dg[N],udg[N];//正反对角线
int n;
void dfs(int x,int y,int s)//s为当前每一行枚举到第几个数
{
if(s>n) return ;
if(y==n) y=0,x++;//切换到下一行
if(x==n)
{
if(s==n)
{
for(int i=0;i<n;i++) cout<<g[i]<<endl;
cout<<endl;
}
return ;
}
g[x][y]='.';
dfs(x,y+1,s);
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
g[x][y] = 'Q';
dfs(x, y + 1, s + 1);
g[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main()
{
cin>>n;
dfs(0,0,0);
return 0;
}
种字打错了
第四天冲冲!