DFS习题(一)

DFS习题(一)

题目一

#include <bits/stdc++.h>
using namespace std;


int n;
int a[15];
//int b[15];
int sum = 0;
int b[10000][11];

void xx(int x) {
    for (int i = 1;i <= n;i++) {
        b[x][i] = a[i];
    }
}
void dfs(int x) {
    if (x>10) {
        int t  = 0;
        for (int i = 1;i <= 10;i++) {
            t += a[i];
        }
        if (t==n) {
            sum++;
            xx(sum);
        }
        return;
    }
    for (int i = 1;i <= 3;i++) {
        a[x] = i;
        dfs(x+1);
        a[x] = 0;
    }
}


int main () {
    cin >> n;
    dfs(1);
    cout << sum << endl;
    //dfs_1(1);
    for (int i = 1;i <= sum;i++) {
        for (int j = 1;j <= 10;j++) {
            cout << b[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

题目二

#include <bits/stdc++.h>
using namespace std;


int n,m;
int a[10010];
int b[10010];
int st[10010];
int start = 0;
int k  = 0;
void dfs(int x) {
    if (x > n) {
        if (!start) {
            for (int i = 1;i <= n;i++) {
                if (b[i] != a[i]) return;
            }
            start=1;
        }else {
            k++;
            if (k == m) {
                for (int i = 1;i <= n;i++) {
                    cout << b[i] << " ";
                }
                exit(0);
            }
        }
        return ;

    }

    for (int i = 1;i <= n;i++) {
            // 设置初始状态
        if (!start) {
            i = a[x];
        }
        if (!st[i]) {
            b[x] = i;
            st[i] = 1;
            dfs(x+1);
            st[i] = 0;
            b[x] = 0;
        }
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    dfs(1);
}

题目三

#include <bits/stdc++.h>
using namespace std;

int num[10010] = {6,2,5,5,4,5,6,3,7,6};
int n;
int ans = 0;
int st[5];
int k = 0;

int cal(int x) {
    if (num[x] > 0) return num[x];
    else {
        int sumFire = 0;
        while (x) {
            sumFire += num[x%10];
            x /= 10;
        }
        return sumFire;
    }
}

void dfs(int x,int sum) {
    if (sum > n) return;
    if (x > 3) {
        if (st[1] + st[2] == st[3] && sum == n) {

            ans++;
        }
        return;
    }
    for (int i = 0;i <= 1000;i++) {
        st[x] = i;
        dfs(x+1,sum+cal(i));
        st[x] = 0;
    }
}
int main () {
    cin >> n;
    n-=4;
    dfs(1,0);
    cout << ans;
}

题目四

#include <bits/stdc++.h>
using namespace std;

int n;
int s[15],k[15];

int st[15];
int max_num = 1e9;
void dfs(int x) {

    if (x > n) {
        int total_s = 1;
        int total_k = 0;
        int tt = 0;
        for (int i = 1;i <= n;i++) {
            if (st[i] == 1) {
                total_s *= s[i];
                total_k += k[i];
                tt++;
            }
        }
        if (tt)
            max_num = min(abs(total_k-total_s),max_num);
        return ;
    }
    st[x] = 1;
    dfs(x+1);
    st[x] = 0;

    st[x] = 2;
    dfs(x+1);
    st[x] = 0;
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> s[i] >> k[i];
    }
    dfs(1);
    cout << max_num;
}

题目五

#include <bits/stdc++.h>
using namespace std;

int n,a,b;
int k[210];
int ans = 1e9;
int judge = 0;

bool st[210];
void dfs(int x,int step) {
    //if (x > n || x < 1) return;
    if (x == n) {
        ans = min(ans,step);
        judge = 1;
        return ;
    }
    // 上
    st[x] = true;
    if (x+k[x] <= n && !st[x+k[x]]){
        st[x+k[x]] = true;
        dfs(x+k[x],step+1);
        st[x+k[x]] = false;
    }

    if (x-k[x] > 0 && !st[x-k[x]]){
        st[x-k[x]] = true;
        dfs(x-k[x],step+1);
        st[x-k[x]] = false;
    }

}
int main () {
    cin >> n >> a >> b;
    for (int i = 1;i <= n;i++) {
        cin >> k[i];
    }
    dfs(a,0);
    if (judge) cout << ans;
    else cout << -1;
}