雙向搜尋(bfs,dfs)

雙向搜尋的基本思路：

雙向搜尋

從狀态圖上的起點和終點同時開始進行廣搜或深搜，如果發現搜尋的兩端相遇了，那麼可以認為是獲得了可行解

BFS例題：

字串變換

代碼：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
#define  SI unordered_map<string, int>
using namespace std;

const int N = 6;

int n;
string a[N], b[N];

int extend(queue<string>& q, SI& da, SI& db, string a[], string b[]){
	//一次周遊一層,大小為q.size()
    for (int k = 0, sk = q.size(); k < sk; k ++ ){
        string t = q.front(); q.pop();

        for (int i = 0; i < t.size(); i ++ )
            for (int j = 0; j < n; j ++ )
                if (t.substr(i, a[j].size()) == a[j]){//可替換
                    string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                    if (da.count(state)) continue;
                    //兩個方向會師,一定是最小步數,直接傳回即可
                    if (db.count(state)) return da[t] + 1 + db[state];
                    da[state] = da[t] + 1;
                    q.push(state);
                }
    }
    return 11;
}

int bfs(string A, string B){
    queue<string> qa, qb;//分别從起點,終點開始的隊列
    SI da, db;//每個狀态到起點的距離da(哈希表),每個狀态到終點的距離db(哈希表)
    qa.push(A), da[A] = 0;
    qb.push(B), db[B] = 0;

    while (qa.size() && qb.size()) {
        int t;
		//看從上到下還是從下到上好
        if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);
        else t= extend(qb, db, da, b, a);
		//找到了
        if (t <= 10) return t;
    }
	//找不到
    return 11;
}

int main(){
    string A, B;
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n ++ ;

    int step = bfs(A, B);
    if (step > 10) puts("NO ANSWER!");
    else printf("%d\n", step);

    return 0;
}
           

DFS例題：

送禮物

思路：

雙向搜尋，先将一部分的禮物能出現的組合打表，對于後一部分，搜尋到一種組合後，再在前一部分的組合中找合适的組合，兩個組合加起來重量<=w，取max就是答案

代碼：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 46;

int n, m, k;
int w[N];
int weights[1 << 25], cnt = 1;
int ans;

void dfs1(int u, int s){//第一次爆搜
    if (u == k){
        weights[cnt ++ ] = s;
        return;
    }
    dfs1(u + 1, s);//不放
    if ((LL)s + w[u] <= m) dfs1(u + 1, s + w[u]);//放進去(帶剪枝)
}

void dfs2(int u, int s){
    if (u == n){
        int l = 0, r = cnt - 1;
        while (l < r){
            int mid = l + r + 1 >> 1;
            if ((LL)s + weights[mid] <= m) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, s + weights[l]);
        return;
    }
    dfs2(u + 1, s);//不放
    if ((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);//放進去(帶剪枝)
}

int main(){
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];
    sort(w, w + n);
    reverse(w, w + n);
    //實踐出真理,用n/2+2代替n/2竟然可以快500+ ms
    k = n / 2 + 2;
    dfs1(0, 0);
    sort(weights, weights + cnt);
	//去重+得到數量(unique傳回類似指針的疊代器)
    cnt = unique(weights, weights + cnt) - weights;
    dfs2(k, 0);
    cout << ans << endl;
    return 0;
}