[AcWing算法提高课]之搜索 双端队列广搜+双向广搜+迭代加深+双向深搜（C++题解）

#include 
#include 
#include 
#include 

using namespace std;
using T = pair;

const int N = 510, inf = 0x3f;

char g[N][N];
int st[N][N], dist[N][N];
//dxdy表示坐标点的方向,因为只能斜着走,所以每次偏移量是|2|
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
//ixiy代表每次从坐标点跨越格点所经过的字符(\或/) 的偏移
/*
进一步解释为:第一个方格的\线所代表的坐标为(0,0) 其跨越了坐标点(0,0)到(1,1)
即dxdy为坐标点偏移 ixiy为格点偏移
*/
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
int k, n, m;

int bfs()
{
    //多组测试数据 每次都要初始化
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    //起始点要初始化为0
    dist[0][0] = 0;

    //根据四个方向偏移 所能走到的四种电路的形状 分别为: 左上\ 右上 / 右下 \ 左下 / 这里要转义
    char cs[5] = "\\/\\/";

    deque q;
    q.push_front({0, 0});

    while(q.size()){
        auto t = q.front();
        q.pop_front();

        int a = t.first, b = t.second;
        /*注意
            双端队列中存储的是坐标点的坐标,即dxdy偏移下的坐标
            所以最终会走到右下角的那个 '点' 不是格子 所以走到(n, m)时返回
        */
        if(a == n && b == m) return dist[n][m];

        if(st[a][b]) continue;
        st[a][b] = true;

        for(int i = 0; i < 4; i ++ ){
            //坐标点偏移
            int u = a + dx[i], v = b + dy[i];
            if(u < 0 || v < 0 || u > n || v > m) continue;

            //格点偏移 即经过坐标点偏移后所经过的格点
            int ga = a + ix[i], gb = b + iy[i];
            //检查所经过的格点是不是我们想要的、连通的那种格点
            int w = (g[ga][gb] != cs[i]);
            //如果是 则距离算为0 如果不是,即需要旋转一下才能连通 则距离算为1
            int d = dist[a][b] + w;
            //如果新扩展的坐标点可以被更新 就入队
            if(d < dist[u][v]){
                dist[u][v] = d;
                //由双端队列广搜的解法 如果扩展的这条边为1 就加入队尾 如果是0就加入对头
                if(!w) q.push_front({u, v});
                else q.push_back({u, v});
            }
        }
    }
    return -1;
}

int main()
{
    cin >> k;
    while(k -- )
    {
        cin >> n >> m;
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ )
                cin >> g[i][j];

        //这一步是为什么 参考yls的视频讲解
        if(n + m & 1) puts("NO SOLUTION");
        else printf("%d\n", bfs());
    }
    return 0;
}

作者：djn
链接：https://www.acwing.com/solution/content/82459/
来源：AcWing
著作权归作者所有。
商业转载请联系作者获得授权，非商业转载请注明出处。

 核心思想：

 实现流程：

        全局和main函数

1. 定义string A,B 为全局变量，并在main函数中进行 输入
2. 由于题目说了，最多只有6个规则，所以在全局开一个大小为6的数组 string a[ ]  string b[ ]，表示 a->b 的规则，并在main函数用while循环输入，并用一个变量n，来记录规则的总数
3. 在main函数中调用bfs函数

        bfs函数实现

1. 特判：如果string A==string B，那么证明此时不需要规则变换，return 0，表示需要变换的步数为0
2. 定义queue qa,qb 来记录 变换后的 string A 和 string B，那么这两个队列的初始情况就是A入qa队 ，B入qb队，各自代表它们的初始状态
3. 定义unordered_map 来 记录 由 由初始的 string A 到现在哈希表中的 string键，距离为 int：多少步的意思，B同理
4. 理解了 （3），那么就能明白 哈希表的 初始化的意义，将初始状态存入哈希表，那么因为它并灭有改变，所以赋值为 0
5. while 循环 继续的条件 ，两个队列均不为空，由上述的 （2）可知，qa和qb代表的是变换后的string A,B,  那么只要它们有一个为空，那么都是不能完成的变换的
6. 然后关于扩展，应该选择扩展数少的进行扩展，因为此时它的分支更少
7. 扩展的同时记录步数，并根据步数的情况进行判断

        extend函数实现

1. 取出队头元素，并删除
2. while 循环继续的条件 队列不空
3. 枚举 ： 外层 i从string t的哪一个位置开始枚举 ，内层 j 枚举规则
4. 判断相等
5. 得到变换后的string
6. 如果db的 中的stirng 也存在 同样的string 那么就 相当于两个方向会师，返回步数
7. 如果曾经在 da中出现 ，那么就 continue
8. da 记录距离+1
9. 入队

 代码实现：

#include
#include
#include
#include
#include
#include 
using namespace std;

const int N = 6;
int n;
string a[N], b[N];
// 扩展函数
// 参数：扩展的队列，到起点的距离，到终点的距离，规则，规则
//返回值：满足条件的最小步数
int extend(queue& q, unordered_map& da, unordered_map& db,
    string a[], string b[])
{
    // 取出队头元素
    string t = q.front();
    q.pop();

    for (int i = 0; i < t.size(); i++)  // t从哪里开始扩展
        for (int j = 0; j < n; j++) // 枚举规则
            //如果t这个字符串的一段= 规则，比如= xyz，才可以替换
            if (t.substr(i, a[j].size()) == a[j])
            {
                // 变换之后的结果state:前面不变的部分+ 变化的部分 + 后面不变的部分
                // 比如abcd ，根据规则abc--> xu，变成 xud，这里的state就是xud
                string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                // state状态是否落到b里面去，两个方向会师，返回最小步数
                if (db.count(state)) return da[t] + 1 + db[state];
                // 如果该状态之前已扩展过，
                if (da.count(state)) continue;
                da[state] = da[t] + 1;
                q.push(state);
            }
    return 11;

}
// 从起点和终点来做bfs
int bfs(string A, string B)
{
    if (A == B) return 0;
    queue qa, qb; // 两个方向的队列
    //每个状态到起点的距离da（哈希表），每个状态到终点的距离db哈希表
    unordered_map da, db;
    // qa从起点开始搜，qb从终点开始搜
    qa.push(A), da[A] = 0; // 起点A到起点的距离为0
    qb.push(B), db[B] = 0; // 终点B到终点B的距离为0

    // qa和qb都有值，说明可以扩展过来，否则说明是不相交的
    while (qa.size() && qb.size())
    {
        int t; // 记录最小步数
        // 哪个方向的队列的长度更小一些，空间更小一些，从该方向开始扩展，
        // 时间复杂度比较平滑,否则有1个点会超时
        if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b);
        else t = extend(qb, db, da, b, a);
        // 如果最小步数在10步以内

        if (t <= 10) return t;
    }

    return 11; // 如果不连通或者最小步数>10，则返回大于10的数

}

int main()
{
    string A, B;
    cin >> A >> B;
    // 读入扩展规则，分别存在a数组和b数组
    while (cin >> a[n] >> b[n]) n++;
    int step = bfs(A, B);
    if (step > 10) puts("NO ANSWER!");
    else cout << step << endl;
}

 题目概述：

给定一个n，求处满足最小序列长度为m的序列

该序列满足以下条件： 

（1）单调递增

（2）后一个数可由 前面的两个数 用加法表示 出来 （一个数可以被使用多次）

（3）第一项一定为1

（4）第m项一定为n

核心思路：

1. 不难想到要用dfs进行暴力搜索
2. 确定参数--->>(int u,int k) -->其中u表示的是当前层数（当前已有项数的）k表示（最大层数）
3.  dfs的返回类型为bool 值，如果为false，那么就证明 构造失败，需要更新最大层数，即k++
4. 如果为true，那么就证明构造成功，打印path数组  （记录路径）

剪枝优化：

1. 开一个bool 数组排除 等效冗余：如果 这个数之前构造过了，那么就continue
2. 从后向前枚举：剪枝顺序优化，因为 从小往大数 有很多分支 ，从大往小 的分支 就会少很多
3. 排除不合理的情况：因为这个序列是单调递增的，所以枚举出来的这个数 一定要大于 它的前一项，并且要小于 n（因为n是最后一项的数）

完整代码：

#include
#include
#include
using namespace std;

const int N = 110;
int n;
int path[N];

bool dfs(int u, int k)//u表示当前层数 k表示最大的层数
{
	if (u == k) return path[u - 1] == n;

	bool st[N] = { 0 };//通过bool 数组排除等效冗余

	for (int i = u - 1; i >= 0; i--)//从后向前枚举：剪枝顺序优化的一种
	{
		for (int j = i; j >= 0; j--)
		{
			int s = path[i] + path[j];
			if (s > n || s <= path[u - 1] || st[s]) continue;//path一定是递增的
			
			st[s] = true;
			path[u] = s;

			if (dfs(u + 1, k)) return true;
		}
	}
	return false;
}

int main()
{
	path[0] = 1;
	while (cin >> n, n)
	{
		int k = 1;
		while (!dfs(1, k)) k++;//如果不满足，那么就增加最大的层数
		for (int i = 0; i < k; i++)
		{
			cout << path[i] << " ";
		}
		cout << endl;
	}

	return 0;
}

 核心思路：

1. 将物品件数砍半（k=n/2）
2. dfs1枚举 前半部分（从0开始到k）
3. dfs2枚举后半部分（从k到n）
4. 在dfs2中记录最大的res

剪枝优化：

1. 在dfs1之前，先逆向排序存放物品重量的数组，使得后序扩展的分支减少
2. 在dfs1中，用weight存 枚举到 第k件物品的所有方案数
3. 在dfs2之前，将weight数组进行排序（正序）（为了二分）
4. 在dfs2之前，将weight数组进行去重（为了二分）
5. 子在dfs2中 如果枚举到了第 n件物品，那么就二分查找满足 的weight[i]，并记录

完整代码：

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 1 << 24;

int n, m, k;
int g[50], weights[N];
int cnt = 0;
int ans;


void dfs1(int u, int s)
{
    if (u == k)//枚举完了一半的
    {
        weights[cnt++] = s;//记录方案数
        return;
    }

    if ((LL)s + g[u] <= m) dfs1(u + 1, s + g[u]);//满足条件-->>选
    dfs1(u + 1, s);//不选
}


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 (weights[mid] + (LL)s <= m) l = mid;
            else r = mid - 1;
        }
        if (weights[l] + (LL)s <= m) ans = max(ans, weights[l] + s);

        return;
    }

    if ((LL)s + g[u] <= m) dfs2(u + 1, s + g[u]);//选
    dfs2(u + 1, s);//不选
}


int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i++) cin >> g[i];

    sort(g, g + n);
    reverse(g, g + n);//逆向：剪枝顺序优化

    k = n / 2;  // 防止 n = 1时，出现死循环
    dfs1(0, 0);//第一次

    sort(weights, weights + cnt);//正向

    //去重
    int t = 0;
    for (int i = 1; i < cnt; i++)
        if (weights[i] != weights[i - 1])
            weights[t++] = weights[i];
    cnt = t;

    dfs2(k, 0);//从一半开始枚举

    cout << ans << endl;

    return 0;
}