BFS进阶技巧——多源BFS、最小步数模型、双端队列广搜、双向广搜

BFS进阶技巧——多源BFS、最小步数模型、双端队列广搜、双向广搜 多源BFS

多源BFS时有从多个源点出发的bfs算法,只需要将多个源点都连一条边权为0的边到虚拟源点,那么问题就等价于从虚拟源点开始BFS。

一开始直接将所有源点加入BFS的队列即可.

矩阵距离

输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

思路

题意为搜索所有0点到一群1点的最短曼哈顿距离。

将所有为1的点直接加入bfs队列，向外搜索，由bfs性质到达的点一定离虚拟源点最短,而到虚拟源点的距离 == 到1点的距离,故最短。

代码

#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 1010;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n,m;
char g[N][N];
int dist[N][N];
PII q[N * N];


void bfs(){
    int hh = 0,tt = -1;
    memset(dist,-1,sizeof dist);
    for(int i = 0; i < n; ++ i){
        for(int j = 0; j < m; ++ j){
            if(g[i][j] == '1'){// '1'
                dist[i][j] = 0;
                q[++ tt] = {i,j};
            }
        }
    }
    while(hh <= tt){
        PII t = q[hh ++];
        for(int i = 0; i < 4; ++ i){
            int a = t.x + dx[i],b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m)continue;
            if(dist[a][b] != -1) continue;
            dist[a][b] = dist[t.x][t.y] + 1;
            q[++ tt] = {a,b};
        }
    }
}


int main(){
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; ++ i){
        scanf("%s",g[i]);
       
    }
    bfs();
    for(int i = 0; i < n; ++ i){
        for(int j = 0; j < m; ++ j){
            printf("%d ",dist[i][j]);
        }
        printf("n");
    }
    
    
}

最小步数模型

BFS可以求各种广义最短路。直接看例题

魔板

Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。

这是一张有 88 个大小相同的格子的魔板：

1 2 3 4
8 7 6 5

我们知道魔板的每一个方格都有一种颜色。

这 88 种颜色用前 88 个正整数来表示。

可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。

对于上图的魔板状态，我们用序列 (1,2,3,4,5,6,7,8)来表示，这是基本状态。

这里提供三种基本 *** 作，分别用大写字母 A，B，C 来表示（可以通过这些 *** 作改变魔板的状态）：

A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。

下面是对基本状态进行 *** 作的示范：

A：

8 7 6 5
1 2 3 4

B：

4 1 2 3
5 8 7 6

C：

1 7 2 4
8 6 3 5

对于每种可能的状态，这三种基本 *** 作都可以使用。

你要编程计算用最少的基本 *** 作完成基本状态到特殊状态的转换，输出基本 *** 作序列。

注意：数据保证一定有解。

输入格式

输入仅一行，包括 88 个整数，用空格分开，表示目标状态。

输出格式

输出文件的第一行包括一个整数，表示最短 *** 作序列的长度。

如果 *** 作序列的长度大于0，则在第二行输出字典序最小的 *** 作序列。

数据范围

输入数据中的所有数字均为 11 到 88 之间的整数。

输入样例：

2 6 8 4 5 7 3 1

输出样例：

7
BCABCCB

思路

用数组存输入数据， *** 作手推一下就行了。

每做一次变换就算一步，在bfs每轮中进行三种 *** 作。为了满足最小字典序要按A,B,C的顺序 *** 作, *** 作后的状态如果没有访问过则进入队列，记录。

注意答案要 *** 作顺序，所以要记录每个 *** 作的上一步 *** 作，最后逆向输出即可。

如果学过群论，那么可以知道本题的三种置换在魔板上构成S8的子群(结合律,逆元,单位元,有限性)

代码

#include 
#include 
#include 
#include 

using namespace std;

typedef pair PII;
const int N = 1e6;

int g[2][4];

string start,tar;//@不要用end命名

unordered_mapdist;//到string状态用的步数
unordered_map>pre;// 变化到键的状态的 *** 作是char存储，键状态的前一个状态是值里的string存贮

string q[N];//队列

string move0(string st){
    string res = st;
    reverse(res.begin(),res.end());
    return res;
}

string move1(string t)
{
    for(int i=0;i<3;i++) swap(t[3],t[i]);
    for(int i=4;i<7;i++) swap(t[i],t[i+1]);
    return t;
}

string move2(string st){
    string res = st;
    swap(st[1],st[6]);
    swap(st[5],st[6]);
    swap(st[2],st[5]);
    return st;
}

int bfs(){
    if(start == tar)return 0;
    q[0] = start;
    int hh = 0,tt = 0;
    dist[start] = 0;
    while(hh <= tt){
        string t = q[hh ++];
        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);
        //按照ABC三种操作的顺序BFS正好能找到最小字典序
        //因为bfs的过程就保证了是按最小字典序找的，A操作的后续必然先扩展，先加入队列，之后是B,C

        //下面看的都是将要转移的状态
        for(int i = 0; i < 3; ++ i){
            if(!dist.count(m[i])){//状态没有被访问过
            //!count(m[i])
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i,t};//m[i]由A + i操作转移过来
                q[++ tt] = m[i];
                if(m[i] == tar) return dist[tar];
            }
        }
    }
    return -1;
}

int main()
{
    for(int i = 0; i < 8; ++ i){
        int t;cin >> t;
        tar += char(t + '0');//+ '0'
    }
    start = "12345678";
    int step = bfs();
    cout << step << endl;
    string res;
    
    while(tar != start){
        res += pre[tar].first;//取操作（逆序）
        tar = pre[tar].second;//变上一个状态
    }
    reverse(res.begin(),res.end());
    if(step > 0)cout << res << endl;
    
    return 0;
}

双端队列广搜

双端队列广搜主要解决图中边的权值只有0或者1的最短路问题，注意和多源BFS不一样，这种是无法用连虚拟源点那种做法的。

双端队列广搜中，边权为0的点放到队头，边权为1的点放到队尾，这样队列仍然满足单调性，且形式上和普通广搜一样，前面的点和后面的点距离相差为1。

普通bfs判断终点，在入队就时就能算出最小距离，双端队列广搜必须在出队时才知道点的最小值。因为有可能终点入队是被距离为1的边入的，后面的点可能会搜到离终点距离为0的边让其入队，故入队时不一定是最小距离，但出队时一定是。

电路维修

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 R 行 C 列的网格（R,C≤500），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。

第一行包含一个整数 T，表示测试数据的数目。

对于每组测试数据，第一行包含正整数 R 和 C，表示电路板的行数和列数。

之后 R 行，每行 C 个字符，字符是"/"和""中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。

数据范围

1≤R,C≤500
1≤T≤5

输入样例：

1
3 5
\/\
\///
/\

输出样例：

1

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

思路

找到最少的开关让电路联通的问题，我们设开关动一次算边权为1，不动算边权为0，则问题等价于找到一条最短路。

图中给出格子和我们的图之间需要换算，因为路的节点是在格点上，而路（开关）在格子中。具体关系为

d x ， d y dx，dy dx，dy用于到达点的方向遍历， i x ， i y ix，iy ix，iy用于到点所用的边（开关）的方向遍历。

另外，开关每次让横纵坐标之和变化偶数，故从（0，0）点只能到达横纵坐标之和为偶数的点，故当n+m为奇可直接排除。

还有一些细节见代码注释。

代码

#include 
#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef pair PII;

const int N = 510,M = N * N;

int n,m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs(){
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0][0] = 0;
    deque q;//双端队列
    q.push_back({0,0});
    
    char cs[] = "\/\/";//需要转义字符。当前点走到4个方向的点理想状态下格子形状(边权是0的状态)
    int dx[4] = {-1,-1,1,1};dy[4] = {-1,1,1,-1};//方向
    int ix[4] = {-1,-1,0,0};iy[4] = {-1,0,0,-1};//格点相对于中心点的偏移
    //https://cdn.acwing.com/media/article/image/2020/10/02/7416_260b418204-8f4c96e579549999453c9467edbbe41.png

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

        if(st[t.x][t.y])continue;
        st[t.x][t.y] = true;
        //@ 要访问四个方向的开关，而是不是交点（线上的点）。每个交点能够被四个开关找到，也就是可以被不重复访问四次。（a，b）是交点的位置，所以在循环中st[a][b]不能拿来判重,（ca，cb)是开关的位置，所以st[ca][cb]可以拿来判重。这里直接在入队时看交点有没有被“访问过”，交点被“访问过”是指四个方向的开关都看过了，
        //距离严格变小才能进入队列，因此之前走过的点不会进入再次队列中
        //看交点的四个开关
        for(int i = 0; i < 4; ++ i){
            int a = t.x + dx[i],b = t.y + dy[i];//要去的点的位置
            if(a < 0 || a > n || b < 0 || b > m) continue;
            int ca = t.x + ix[i],cb = t.y + iy[i];//开关的位置
            
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);//不同则需要翻转，+1
            if(dist[a][b] > d){
                dist[a][b] = d;
                if(g[ca][cb] != cs[i])q.push_back({a,b});
                else q.push_front({a,b})//插入队头
            }
        }
    }

    return dist[n][m];

}

int main(){
    int T;
    scanf("%d",&T);
    while(T --){
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++ i)scanf("%s",g[i]);
        int t = bfs();
        if(t == 0x3f3f3f3f)puts("NO SOLUTION");
        else printf("%dn",t);
    }

    return 0;
}

双向广搜

单向广搜随着步数增多搜索点数呈指数级增加，双向在一般情况下能够降低数量级，视图如下：

双向BFS每次必须搜一层，如果每次只搜一个，可能会出现如下情况：

两个方向都搜了一个，搜到就确认是最小值，但实际上可能存在更优的虚线路径。

字串变换

已知有两个字串 AA, BB 及一组字串变换的规则（至多 66 个规则）:

A1→B1A1→B1

A2→B2A2→B2

…

规则的含义为：在 AA 中的子串 A1A1 可以变换为 B1B1、A2A2 可以变换为 B2…B2…。

例如：AA＝abcd BB＝xyz

变换规则为：

abc` →→ `xu` `ud` →→ `y` `y` →→ `yz

则此时，AA 可以经过一系列的变换变为 BB，其变换的过程为：

abcd` →→ `xud` →→ `xy` →→ `xyz

共进行了三次变换，使得 AA 变换为 BB。

输入格式

输入格式如下：

AA BB
A1A1 B1B1
A2A2 B2B2
… …

第一行是两个给定的字符串 AA 和 BB。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 2020。

输出格式

若在 1010 步（包含 1010 步）以内能将 AA 变换为 BB ，则输出最少的变换步数；否则输出 NO ANSWER!。

输入样例：

abcd xyz
abc xu
ud y
y yz

输出样例：

3

思路

从A串向B搜索，也从B向A搜索，共用搜索规则。

搜索时有个trick，每次搜队列中元素少的，也就是先搜分至少的方向。能让两端的搜索树更均衡。

替换使用substr函数，substr的第二个参数是长度不是位置，不填表示取后面的全部。

代码

#include 
#include 
#include 
#include 

using namespace std;

string A,B;
string a[10],b[10];

int n;
//双向bfs每次必须扩展一层https://www.acwing.com/activity/content/code/content/132167/
int extend(queue& q,unordered_map& da,unordered_map&db,string a[],string b[]){//!引用
    int d = da[q.front()];
    
    while(q.size() && da[q.front()] == d){//第一个判断保证有有点可搜索，第二个判断队首元素还在d这一层
    
        auto t = q.front();
        q.pop();
        
        for(int i = 0; i < n; ++ i){//遍历n个规则
            for(int j = 0; j < t.size(); ++ j){//枚举子串
                if(t.substr(j,a[i].size()) == a[i])//相同可替换时
                {
                    //!substr第二个参数是向后延伸的位数不是位置
                    string r = t.substr(0,j) + b[i] + t.substr(j + a[i].size());//substr加一个参数就是从参数到结尾
                    //最后不能用b[i].size()，因为t串中原来是a的长度
                    if(da.count(r))continue;//重复
                    if(db.count(r))return da[t] + db[r] + 1;//搜到相同位置，
                    
                    da[r] = da[t] + 1;
                    q.push(r);
                }
            }
        }
        
    }
    return 11;
        
}
int bfs()
{
    if (A == B) return 0;//!
    unordered_map da,db;
    queueqa,qb;
    qa.push(A);
    qb.push(B);
    da[A] = db[B] = 0;
    int step = 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;
        if(++ step == 10)return - 1;//先++再比较，第10次才会成立
    }
    
    
    return -1;
    
}

int main(){
    
    cin >> A >> B;
    while(cin >> a[n] >> b[n])n ++;
    
    int step = bfs();
    if(step == -1)puts("NO ANSWER!");
    else printf("%dn",step);
    
    return 0;
    
}