迭代深搜简单来说就是限制深度的深搜,这样就可以避免像广搜一样占用大量空间,又可以像广搜找到最佳的路径。

两道例题

1.埃及分数

#include<cstdio>
#include<set>
#include<cstring>
using namespace std;

const int N = 10;
typedef long long LL;

set<LL>s;
LL now[N], pre[N];
bool flag;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a%b) : a;
}

bool good(int k) {//比较出较好的结果
    for (int i = k; i>0; i--) {
        if (now[i] != pre[i]) {
            return pre[i] == 0 || now[i] < pre[i];
        }
    }
    return 0;
}

void dfs(LL a, LL b, int k, int dep) {
    if (k == dep) {
        if (b%a ||b/a<=now[k-1]||s.count(b/a)) {
            return;
        }
        now[k] = b / a;
        if (!flag || good(k)) {
            memcpy(pre, now, sizeof(now));
        }
        flag = 1;
        return;
    }
    LL j = b / a;
    if (j <= now[k - 1]) {
        j = now[k - 1] + 1;
    }
    LL t = (dep - k + 1)*b / a;//如果不满足,那么永远不可能有结果,所以就可以限制上限
    for (LL i = j; i <= t; i++) {
        if (s.count(i)) {
            continue;
        }
        now[k] = i;
        LL m = gcd(a*i - b, b*i);
        dfs((a*i - b) / m, b*i / m, k + 1, dep);
    }
}

void fun(LL a, LL b) {
    now[0] = 1;
    for (int dep = 2; dep <= N; dep++) {
        dfs(a, b, 1, dep);
        if (flag) {
            for (int i = 1; i <= dep; i++) {
                if (i != dep) {
                    printf("1/%lld+", pre[i]);
                }
                else {
                    printf("1/%lld", pre[i]);
                }
            }
            printf("\n");
            return;
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        memset(now, 0, sizeof(now));
        memset(pre, 0, sizeof(pre));
        s.clear();
        LL a, b;
        int k, t;
        flag = 0;
        scanf("%lld%lld%d", &a, &b, &k);
        while (k--) {
            scanf("%d", &t);
            s.insert(t);
        }
        printf("Case %d: %lld/%lld=", i, a, b);
        fun(a, b);
    }
    return 0;
}

2.

这道题没有过oj,就纯过了样例,但重要的是理解迭代深搜的思想。

#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;

int arr[8][8];
int num;
vector<char> vec;

char name(int x, int y, int dir) {
    if (y) {
        if (dir == -1) {
            if (y == 2) {
                return 'A';
            }
            else {
                return 'B';
            }
        }
        else if (dir == 1) {
            if (y == 2) {
                return 'F';
            }
            else {
                return 'E';
            }
        }
    }
    else if (x) {
        if (dir == 1) {
            if (x == 2) {
                return 'C';
            }
            else {
                return 'D';
            }
        }
        else if (dir == -1) {
            if (x == 2) {
                return 'H';
            }
            else {
                return 'G';
            }
        }
    }
}

int judge() {
    int x = arr[2][2];
    for (int j = 2; j <= 4; j += 2) {
        for (int i = 2; i <= 4; i++) {
            if (arr[j][i] != x) {
                return 0;
            }
        }
    }
    for (int i = 2; i <= 4; i += 2) {
        if (arr[3][i] != x) {
            return 0;
        }
    }
    return x;
}

void move(int x, int y, int dir) {
    if (y != 0) {
        if (dir<0) {
            int t = arr[6][y];
            for (int i = 0; i<6; i++) {
                arr[(i + dir + 7) % 7][y] = arr[i][y];
            }
            arr[5][y] = t;
        }
        else if (dir>0) {
            int t = arr[0][y];
            for (int i = 6; i>0; i--) {
                arr[(i + dir + 7) % 7][y] = arr[i][y];
            }
            arr[1][y] = t;
        }
    }
    else if (x != 0) {
        if (dir<0) {
            int t = arr[x][6];
            for (int i = 0; i<6; i++) {
                arr[x][(i + dir + 7) % 7] = arr[x][i];
            }
            arr[x][5] = t;
        }
        else if (dir>0) {
            int t = arr[x][0];
            for (int i = 6; i>0; i--) {
                arr[x][(i + dir + 7) % 7] = arr[x][i];
            }
            arr[x][1] = t;
        }
    }
}

void dfs(int k, int dep) {
    if (k == dep) {
        int j = judge();
        if (j) {
            num = j;
            return;
        }
        return;
    }
    for (int i = 2; i <= 4; i += 2) {
        if (num != -1) {
            return;
        }
        move(0, i, -1);
        vec.push_back(name(0, i, -1));
        dfs(k + 1, dep);
        if (num != -1) {
            return;
        }
        vec.pop_back();
        move(0, i, 1);
    }
    for (int i = 2; i <= 4; i += 2) {
        if (num != -1) {
            return;
        }
        move(i, 0, 1);
        vec.push_back(name(i, 0, 1));
        dfs(k + 1, dep);
        if (num != -1) {
            return;
        }
        vec.pop_back();
        move(i, 0, -1);
    }
    for (int i = 2; i <= 4; i += 2) {
        if (num != -1) {
            return;
        }
        move(0, i, 1);
        vec.push_back(name(0, i, 1));
        dfs(k + 1, dep);
        if (num != -1) {
            return;
        }
        vec.pop_back();
        move(0, i, -1);
    }
    for (int i = 2; i <= 4; i += 2) {
        if (num != -1) {
            return;
        }
        move(i, 0, -1);
        vec.push_back(name(i, 0, -1));
        dfs(k + 1, dep);
        if (num != -1) {
            return;
        }
        vec.pop_back();
        move(i, 0, 1);
    }
}

void iinput(int i) {
    int t;
    for (int j = 2; j <= 4; j += 2) {
        scanf("%d", &t);
        arr[i][j] = t;
    }
}

void input() {
    int t;
    scanf("%d", &t);
    arr[0][5] = t;
    iinput(1);
    for (int i = 0; i<7; i++) {
        scanf("%d", &t);
        arr[2][i] = t;
    }
    iinput(3);
    for (int i = 0; i<7; i++) {
        scanf("%d", &t);
        arr[4][i] = t;
    }
    iinput(5);
    iinput(6);
}

int main() {
    int t;
    while (scanf("%d", &t) != EOF) {
        memset(arr, 0, sizeof(arr));
        arr[0][3] = t;
        num = -1;
        vec.clear();
        input();
        for (int dep = 1; dep <= 10; dep++) {
            dfs(0, dep);
            if (num != -1) {
                break;
            }
            vec.clear();
        }
        for (int i = 0; i<vec.size(); i++) {
            cout << vec[i];
        }
        cout << endl << num << endl;
    }
    return 0;
}
01-21 11:14