2.1.2 BFS中的多源BFS-双端队列BFS-最小步数模型

一. 多源BFS——求解到最近的一个起点的距离

起点不唯一，求到多个源点中距离最短的路径。

注意这和多源最短路是不同的，多源最短路是求到所有源点分别的最短距离，这里求解的是到最近的源点的距离，只取一个值。

这种问题可以转化为单源最短路问题。假想一个“虚拟“源点，从”虚拟“源点到各个起点的距离都是0，然后从”虚拟“源点开始BFS遍历。实际求解释不需要构造这个虚拟源点，只需要刚开始时将所有起点都入队列即可。

1. AcWing 173. 矩阵距离

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 多源BFS——AcWing 173. 矩阵距离
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1010, M = N * N;

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

void bfs(){
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
    int hh = 0 , tt = -1;// 注意这里tt从-1开始
    // 分别标记队列要取出结点的位置，存取结点的前一个位置
    
    memset(dist, -1, sizeof dist);
    // 虚源点的思想，假设所有源点都和虚源点连通，并且距离为0
    // 将所有源点入队列即可
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            if (g[i][j] == '1'){
                q[++ tt] = {i, j};
                dist[i][j] = 0;
            }
            
    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;
            q[++ tt] = {a, b};
            dist[a][b] = dist[t.x][t.y] + 1;
        }
    }
}

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 - 1; ++ j)
            printf("%d ", dist[i][j]);
        printf("%d\n", dist[i][m-1]);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 多源BFS——AcWing 173. 矩阵距离
from collections import deque

def main():
    n, m = map(int, input().split())
    g = [list(input()) for _ in range(n)]
    dist = [[-1] * m for _ in range(n)]
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    def bfs():
        q = deque()
        for i in range(n):
            for j in range(m):
                if g[i][j] == '1':
                    q.append((i, j))
                    dist[i][j] = 0
        
        while q:
            x, y = q.popleft()
            for i in range(4): 
                a, b = x + dx[i], y + dy[i]
                if a < 0 or a >= n or b < 0 or b >= m:
                    continue
                if dist[a][b] != -1:
                    continue
                q.append((a, b))
                dist[a][b] = dist[x][y] + 1

    bfs()
    # for i in range(n):
    #     for j in range(m):
    #         print(dist[i][j], end=" ")
    #     print()
    [print(' '.join([str(x) for x in r])) for r in dist] # 速度快很多

if __name__ == '__main__':
    main()

二. 双端队列BFS——01BFS

边权不唯一，既有0又有1(0 and not 0)

注意建图思想，节点间有两种连通方式，一种不需要操作，一种需要操作且操作花费相同，此时就可以转为01边权。

这种问题可以使用双端队列处理。边权为0的插入队头，边权为1的插入队尾。这样维持了两段性和单调性。

注意这种题目中，一个节点可能会入队多次从而更新多次。当作特殊的dijkstra算法来写。

1.AcWing 175. 电路维修

注意本题的性质——有一半的点不可达。与起点行列和的奇偶性不同的节点，就不可达。原因在于斜着走奇偶坐标一定是同时加减变化。这种性质保证了不会同时走一个方格中的两个对角线方向，从而电路一定是连通的，从而才能使用BFS解决这道题。否则使用BFS可能不符题意。

需要将 「电线所在方格的四个点」 与 「方格坐标」 对应起来，因此在这里引入了 两对对应的下标偏移~

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 双端队列BFS——AcWing 175. 电路维修 
// 边权不唯一，既有0又有1(0 and not 0)
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 510, M = N * N;

int n, m;
char g[N][N];
int dist[N][N];
// 这里要注意g[N][N]存的是边的状态图，而dist[N][N]存的是节点间的距离
// 因此两者的坐标是不同的，前者是边的坐标，后者是节点的坐标，不能混淆，需要分别进行定义表示
bool st[N][N];
// 类似dijkstra算法，一个节点会多次入队，需要判重数组，防止多次更新

int bfs(){
    memset(dist, 0x3f, sizeof dist); // 初始距离为无穷大
    memset(st, 0, sizeof st);
    dist[0][0] = 0;
    deque<PII> q;
    q.push_back({0, 0});

    char cs[] = "\\/\\/"; // 四个方向通路时的状态，以左上角方格为起点顺时针记录，呈 X 型
    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}; // 边的对应坐标，注意这里的相对坐标也是相对节点而言的，因为入队的是节点
    // 指此方向的电线将经过的田子格（边状态），以左上角方格顺时针编号

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

        if (st[t.x][t.y]) continue; // 不重复更新，类堆优化 Dijkstra 的判重方式
        st[t.x][t.y] = true;

        // 对电线的走向、走过的方格进行遍历
        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;
            // 注意这里上界是n和m，而不是n-1和m-1

            int ca = t.x + ix[i], cb = t.y + iy[i]; // 边的坐标->读边的当前状态
            int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
            // 根据边的状态是否是连通状态来判断边权

            if (d < dist[a][b]){ // 只有距离更短才进行更新
                dist[a][b] = d;

                if (g[ca][cb] != cs[i]) q.push_back({a, b});
                else q.push_front({a, b});
                // 边权为0的插入队头，边权为1的插入队尾。这样维持了两段性和单调性。
            }
        }
    }
    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");
        // if (n + m & 1) puts("NO SOLUTION"); 
        // 与起点行列和的奇偶性不同的节点，就不可达
        else printf("%d\n", t);
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# 双端队列BFS——AcWing 175. 电路维修 
# 边权不唯一，既有0又有1(0 and not 0)
from collections import deque

def main():
    T = int(input())
    es = "\\/\\/"
    # 四个方向通路时的状态，以左上角方格为起点顺时针记录，呈 X 型
    d_x, d_y = [-1, -1, 1, 1], [-1, 1, 1, -1]
    # 节点的对应坐标，指经过此方向的电线后可到达的点，以左上角方格顺时针编号
    d_ex, d_ey = [-1, -1, 0, 0], [-1, 0, 0, -1]
    # 边的对应坐标，注意这里的相对坐标也是相对节点而言的，因为入队的是节点
    # 指此方向的电线将经过的田子格（边状态），以左上角方格顺时针编号
    
    def bfs():
        dist = [[1e9] * (m + 1)  for _ in range(n + 1)]
        # 一定注意这里上界是n和m，而不是n-1和m-1
        dist[0][0] = 0
        dq = deque([(0, 0)])
        vis = set()
        # 不重复更新，类堆优化 Dijkstra 的判重方式
        
        while dq:
            x, y = dq.popleft()
            if (x, y) in vis:
                continue
            vis.add((x, y))
            
            for ch, dx, dy, dex, dey in zip(es, d_x, d_y, d_ex, d_ey):
                nx, ny = x + dx, y + dy
                if nx < 0 or nx > n or ny < 0 or ny > m:
                    continue
                ex, ey = x + dex, y + dey
                d = dist[x][y] + int(g[ex][ey] != ch)
                # 根据边的状态是否是连通状态来判断边权
                if d < dist[nx][ny]:
                    dist[nx][ny] = d
                    if g[ex][ey] == ch:
                        dq.appendleft((nx, ny))
                    else:
                        dq.append((nx, ny))
                    # 边权为0的插入队头，边权为1的插入队尾
                    # 这样维持了两段性和单调性
        return dist[n][m]    

    for _ in range(T):
        n, m = map(int, input().split())
        g = [input() for _ in range(n)]
        # 这里要注意g存的是边的状态图，而dist存的是节点间的距离
        res = bfs()
        print("NO SOLUTION" if res == 1e9 else res)

if __name__ == '__main__':
    main()

三. 最小步数模型——状态图中的搜索

最小步数->整体视为一个状态，状态的变换的最小步数(状态本身作为一个点，每次变换视为一步，问题是状态之间的逻辑关系)

以棋盘为例进行说明，最短路模型指求解棋盘中某一点到另一点的最短距离，而最小步数模型将棋盘整体的布局视为一个状态，通过对棋盘进行最少的操作变换得到新的棋局状态

搜索的不是一个具体的图，每个节点不是一个具体的点。每个节点都是一个状态的抽象，边是状态间的变换操作，图是状态转移的有向图。

其本质就是在所有状态构成的状态转换有向图中进行最短距离搜索，只不过状态的具体表示是可千变万化的，需要将具体问题转化为状态转移问题，因为需要重点思考状态的存储表示和变换操作的实现。

这种题目思路相对简单，但代码比较难写

状态图的存储一般使用哈希法（手写哈希函数，康托展开，map）。

由于数组不方便进行存储、逻辑判断等操作，将状态以字符串形式进行存储，但进行变换操作时为了具体形象，需要转换为数组进行操作

eg.八数码

1.AcWing 1107. 魔板

本题是一个重点要掌握的外部搜索的的题。外部表示往往涉及状态表示和状态转移。

本题的两大难点：

  1. 状态表示

  • 如何把状态放到队列里

  • 如何记录每个状态的距离

  1. 状态转移

本题状态表示比较复杂，每个状态都是一个3 X 3的小矩阵。

一种比较简单的方式是使用字符串来表示状态，将二维矩阵转化为一维字符串（展成一行）。入队时使用queue queue，记录距离时使用哈希表unordered_map<string, int> dist。

在进行状态转移时，首先将字符串变回矩阵（可以是想象的），然后进行转移——枚举上下左右，最后将矩阵再变回字符串。

这里要用到一个常用技巧：二维坐标与一维坐标的转换。设矩阵大小为n X m，元素二维坐标为(x, y)(x为行号，y为列号)，一维坐标是k，则：$$x = k / n, y = k % n$$
$$ k = x * n + y$$

注意这里要求一维序列和二维矩阵都要从0开始计数。

按序输出往往意味着在处理时就按照要求的顺序的进行处理，而不是在求解完后再进行排序。本题要求按字典序输出，则我们只需在处理时按"A"、“B”、"C"的顺序进行处理即可。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// BFS之最小步数模型——外部搜索——AcWing 1107. 魔板  
// 写代码时先搭框架再扣细节
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

char g[2][4]; 
// 具体表示当前状态，方便进行转换
unordered_map<string, pair<char, string>> pre;
// 记录操作序列和前一个状态，注意要将操作的类型一并存储
// 需要注意状态图和相关属性的存储使用哈希表，其中每个状态用字符串表示->状态无法直接用坐标刻画，而是有其整体内容刻画
unordered_map<string, int> dist;
// 存取每个状态的变换次数

// 获取当前状态对应的二维矩阵
void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++) g[1][j] = state[i];
    // 注意第二行是反序（正反指数字大小顺序4
    // 我们在字符串表示时，为方便，第二行也使用了正序，但转为矩阵时要变回反序
}

// 获取当前状态对应的一维序列
string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i];
    for (int i = 3; i >= 0; i -- ) res += g[1][i];
    return res;
}

// 分别实现所有操作函数
// 交换上下两行
string move0(string state)
{
    set(state);
    // 转换成二维矩阵
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
    // 返回对应的一维序列
}

// 将最右边的一列插入到最左边
string move1(string state)
{
    set(state);
    // 转换成二维矩阵
    char v0 = g[0][3], v1 = g[1][3];
    // 先把最右边一列抽出
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    // 其余列右移
    g[0][0] = v0, g[1][0] = v1;
    // 将最右边的一列插入到最左边
    return get();
    // 返回对应的一维序列
}

// 魔板中央对的4个数作顺时针旋转
string move2(string state)
{
    set(state);
    // 转换成二维矩阵
    char v = g[0][1];
    // 由于旋转的大小是固定的，直接枚举即可
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
    // 返回对应的一维序列
}

int bfs(string start, string end){
    if (start == end) return 0;
	queue<string> q;
    // string队列
    q.push(start);
    dist[start] = 0;
    // 初始状态入队并标记

    while (!q.empty()) // 队列不为空
    {
        auto t = q.front();
        q.pop();
        // 取出队头元素

        // 枚举所有可能的变换状态
        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for (int i = 0; i < 3; i ++ )
            if (!dist.count(m[i])) // 使用count函数查询是否已被搜寻过
            {
                pre[m[i]] = {'A' + i, t};
                // 记录操作序列和前一个状态
                dist[m[i]] = dist[t] + 1;
                if (m[i] == end) return dist[m[i]];
                // 变换后的状态为目标状态时返回
                q.push(m[i]);
                // 入队  
            }
    }
    return -1;
}

int main()
{
    string start = "12345678", end;
    // 我们在字符串表示时，为方便，第二行也使用了正序，但转为矩阵时要变回反序

    char s[2];
    for (int i = 0; i < 8; ++ i){
        scanf("%s", s);
        end += *s;
    }

    // int x;
    // string start, end;
    // for (int i = 0; i < 8; i ++ )
    // {
    //     cin >> x;
    //     end += char(x + '0');
    //     // 为了方便状态表示，转化为字符
    // }

    // for (int i = 1; i <= 8; i ++ ) start += char('0' + i);

    int step = bfs(start, end);
    // 传入初始状态和目标状态

    cout << step << endl;
    if (step > 0){
        string res;
        // 反向得到搜寻序列
        while (end != start)
        {
            res += pre[end].first;
            end = pre[end].second;
            // 这里注意要使用pair<char, string>才方便倒退
        }

        reverse(res.begin(), res.end());
        // 注意反转

        cout << res << endl;
    }

    return 0;
}
不使用dist
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// BFS之最小步数模型——外部搜索——AcWing 1107. 魔板  
// 写代码时先搭框架再扣细节
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>

using namespace std;

char g[2][4]; 
// 具体表示当前状态，方便进行转换
unordered_map<string, pair<string, string>> pre;
// 记录操作序列和前一个状态，注意要将操作的类型一并存储
// 需要注意状态图和相关属性的存储使用哈希表，其中每个状态用字符串表示->状态无法直接用坐标刻画，而是有其整体内容刻画

// 获取当前状态对应的二维矩阵
void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];
    for (int i = 7, j = 0; j < 4; i --, j ++) g[1][j] = state[i];
    // 注意第二行是反序（正反指数字大小顺序4
    // 我们在字符串表示时，为方便，第二行也使用了正序，但转为矩阵时要变回反序
}

// 获取当前状态对应的一维序列
string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i];
    for (int i = 3; i >= 0; i -- ) res += g[1][i];
    return res;
}

// 分别实现所有操作函数
// 交换上下两行
string move0(string state)
{
    set(state);
    // 转换成二维矩阵
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);
    return get();
    // 返回对应的一维序列
}

// 将最右边的一列插入到最左边
string move1(string state)
{
    set(state);
    // 转换成二维矩阵
    char v0 = g[0][3], v1 = g[1][3];
    // 先把最右边一列抽出
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1];
        g[1][i] = g[1][i - 1];
    }
    // 其余列右移
    g[0][0] = v0, g[1][0] = v1;
    // 将最右边的一列插入到最左边
    return get();
    // 返回对应的一维序列
}

// 魔板中央对的4个数作顺时针旋转
string move2(string state)
{
    set(state);
    // 转换成二维矩阵
    char v = g[0][1];
    // 由于旋转的大小是固定的，直接枚举即可
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = v;
    return get();
    // 返回对应的一维序列
}

void bfs(string start, string end){
	queue<string> q;
    // string队列
    q.push(start);
    pre[start] = {"", ""};
    // 初始状态入队
    string op[3] = {"A", "B", "C"};

    while (!q.empty()) // 队列不为空
    {
        auto t = q.front();
        q.pop();
        // 取出队头元素
        if (t == end) // 变换后的状态为目标状态时返回
            return;

        // 枚举所有可能的变换状态
        string m[3];
        m[0] = move0(t);
        m[1] = move1(t);
        m[2] = move2(t);

        for (int i = 0; i < 3; i ++ )
            if (!pre.count(m[i])) // 使用count函数查询是否已被搜寻过
            {
                pre[m[i]] = {pre[t].first + op[i], t};
                // 记录操作序列和前一个状态
                q.push(m[i]);
                // 入队  
            }
    }
}

int main()
{
    string start = "12345678", end;
    // 我们在字符串表示时，为方便，第二行也使用了正序，但转为矩阵时要变回反序

    char s[2];
    for (int i = 0; i < 8; ++ i){
        scanf("%s", s);
        end += *s;
    }

    bfs(start, end);
    // 传入初始状态和目标状态
    int step = pre[end].first.length();
    cout << step << endl;
    if (step)
        cout << pre[end].first << endl;
    // 注意最后输出时需要先判断，避免第二个换行符
    return 0;
}

python

python对一维序列进行操作比较方便，因此不必转化为二维矩阵。

复杂版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# BFS之最小步数模型——外部搜索——AcWing 1107. 魔板  
#  复杂版
from collections import deque

def main():
    start = "12345678"
    end = "".join(input().split())
    g = [[""] * 4 for _ in range(2)]
    pre, dist = {}, {}
    
    def set(state):
        for i in range(4): 
            g[0][i] = state[i]
        for i in range(4):
            g[1][i]= state[7 - i]
        
    def get():
        res = ""
        for i in range(4):
            res = res + g[0][i]
        for i in range(4):
            res = res + g[1][3 - i]
        return res
        
    def A(state):
        set(state)
        for i in range(4):
            g[0][i], g[1][i] = g[1][i], g[0][i]
        return get()
        
    def B(state):
        set(state)
        v0, v1 = g[0][3], g[1][3]
        for i in range(3, 0, -1):
            g[0][i] = g[0][i - 1]
            g[1][i] = g[1][i - 1]
        g[0][0], g[1][0] = v0, v1
        return get()
            
    def C(state):
        set(state)
        g[0][1], g[0][2], g[1][2], g[1][1] = g[1][1], g[0][1], g[0][2], g[1][2]
        return get()
            
    def bfs():
        q = deque([start])
        pre[start] = ("", "")
        dist[start] = 0
        while q:
            t = q.popleft()
            if t == end:
                return dist[t]
            for op, next in zip("ABC", (A(t), B(t), C(t))):
                if next not in dist:
                    dist[next] = dist[t] + 1
                    pre[next] = (op, t)
                    q.append(next)
        return - 1
            
    step = bfs()
    print(step)
    if step > 0:
        res = ""
        while True:
            if end == start:
                 break
            res += pre[end][0]
            end = pre[end][1]
        print(res[::-1])

if __name__ == '__main__':
    main()
简化版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# BFS之最小步数模型——外部搜索——AcWing 1107. 魔板  
# 简化包含dist版
from collections import deque

def main():
    start, end = "12345678", "".join(input().split())
    # A 操作等价于是翻转原字符串，B、C 操作可以在草稿纸上同理推出
    # 无需转数组，可减少代码量
    A = lambda s: s[::-1]
    B = lambda s: s[3] + s[:3] + s[5:] + s[4]
    C = lambda s: s[0] + s[6] + s[1] + s[3:5] + s[2] + s[5] + s[7]
    pre, dist = {}, {}
    
    def bfs():
        q = deque([start])
        pre[start] = ("", "")
        dist[start] = 0
        while q:
            t = q.popleft()
            if t == end:
                return dist[t]
            for op, next in zip("ABC", (A(t), B(t), C(t))):
                if next not in dist:
                    dist[next] = dist[t] + 1
                    pre[next] = (op, t)
                    q.append(next)
        return - 1
            
    step = bfs()
    print(step)
    if step > 0:
        res = ""
        while True:
            if end == start:
                 break
            res += pre[end][0]
            end = pre[end][1]
        print(res[::-1])

if __name__ == '__main__':
    main()
不含dist的简化版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# BFS之最小步数模型——外部搜索——AcWing 1107. 魔板  
# 不含dist的简化版
from collections import deque

def main():
    start, end = "12345678", "".join(input().split())
    # A 操作等价于是翻转原字符串，B、C 操作可以在草稿纸上同理推出
    # 无需转数组，可减少代码量
    A = lambda s: s[::-1]
    B = lambda s: s[3] + s[:3] + s[5:] + s[4]
    C = lambda s: s[0] + s[6] + s[1] + s[3:5] + s[2] + s[5] + s[7]
    pre = {}
    
    def bfs():
        q = deque([start])
        pre[start] = ("", "")

        while q:
            t = q.popleft()
            if t == end:
                s = pre[t][0]
                return str(len(s)), s
            for op, next in zip("ABC", (A(t), B(t), C(t))):
                if next not in pre:
                    pre[next] = (pre[t][0] + op, t)
                    q.append(next)
        return - 1
            
    print("\n".join(bfs()).strip())
    # 这里最后输出不需要判断操作序列为空的情况是因为strip()去掉了空，避免了第二个换行符

if __name__ == '__main__':
    main()