一、Y总视频进度
二、刷题
2.1 AcWing-842：排列数字
1. 问题描述
2. 问题分析
3. 问题解决
#include
#include
#include
using namespace std;
const int N = 12;
int path[N];
bool flag[N];
int n;
void dfs(int u)
{
// 走到头后执行的操作
if(u == n)
{
for(int i = 0; i < n; i++) cout << path[i] << ' ';
putchar('n');
return ;
}
// 路途中的操作
for(int i = 1; i <= n; i++)
{
if(flag[i] == false)
{
path[u] = i;
flag[i] = true;
// 往下走
dfs(u+1);
// 恢复现场
flag[i] = false;
}
}
}
int main()
{
scanf("%d", &n);
dfs(0);
return 0;
}
2.2 AcWing-843：八皇后
1. 问题描述
2. 问题解决
#include
#include
#include
using namespace std;
const int N = 15;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u)
{
if(u == n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
putchar('n');
return ;
}
for(int i = 0; i < n; i++)
{
if(!col[i] && !dg[u+i] && !udg[i - u + n])
{
g[u][i] = 'Q';
col[i] = dg[u+i] = udg[i-u+n] = true;
dfs(u+1);
col[i] = dg[u+i] = udg[i-u+n] = false;
g[u][i] = '.';
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = '.';
dfs(0);
return 0;
}
