2022-01-06每日刷题打卡

2022-01-06每日刷题打卡 一、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;
}