報(bào)名明年4月藍(lán)橋杯軟件賽的同學(xué)們，如果你是大一零基礎(chǔ)，目前懵懂中，不知該怎么辦，可以看看本博客系列：備賽20周合集
20周的完整安排請(qǐng)點(diǎn)擊：20周計(jì)劃
每周發(fā)1個(gè)博客，共20周。
在QQ群上交流答疑：

第14周: ?BFS

1. BFS簡(jiǎn)介和基本代碼

??第12周博客用“一群老鼠走迷宮”做比喻介紹了BFS的原理，類似的比喻還有“多米諾骨牌”、“野火蔓延”。BFS的搜索過程是由近及遠(yuǎn)的，從最近的開始，一層層到達(dá)最遠(yuǎn)處。以下面的二叉樹為例，一層一層地訪問，從A出發(fā)，下一步訪問B、C，再下一步訪問D、E、F、G，最后訪問H、I。圓圈旁邊的數(shù)字是訪問順序。

??一句話概況BFS的思想：全面擴(kuò)散、逐層遞進(jìn)。
??BFS的逐層訪問過程如何編程實(shí)現(xiàn)？非常簡(jiǎn)單，用隊(duì)列，“BFS = 隊(duì)列”。隊(duì)列的特征是先進(jìn)先出，并且不能插隊(duì)。BFS用隊(duì)列實(shí)現(xiàn)：第一層先進(jìn)隊(duì)列，然后第二層進(jìn)隊(duì)列、第三層、…。
??上面圖示的二叉樹用隊(duì)列進(jìn)行BFS操作：根節(jié)點(diǎn)A第1個(gè)進(jìn)隊(duì)列；然后讓A的子節(jié)點(diǎn)B、C進(jìn)隊(duì)列；接下來讓B、C的子節(jié)點(diǎn)D、E、F、G進(jìn)隊(duì)列；最后讓E、G的子節(jié)點(diǎn)H、I進(jìn)隊(duì)列。節(jié)點(diǎn)進(jìn)入隊(duì)列的先后順序是A-BC-DEFG-HI，正好按層次分開了。
??在任何時(shí)刻，隊(duì)列中只有相鄰兩層的點(diǎn)。
??下面的代碼輸出圖示二叉樹的BFS序，用隊(duì)列實(shí)現(xiàn)。隊(duì)列和二叉樹參考第6周隊(duì)列和第7周二叉樹的講解。
C++代碼

#include <bits/stdc++.h>
using namespace std;
const int N=100;                  
char t[N];                             //簡(jiǎn)單地用一個(gè)數(shù)組定義二叉樹
int ls(int p){return p<<1;}            //定位左孩子，也可以寫成 p*2
int rs(int p){return p<<1 | 1;}        //定位右孩子，也可以寫成 p*2+1
void bfs(int root) {queue<int> q;                      //定義隊(duì)列q.push(root);                      //第一個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列while (!q.empty()) {               //用BFS訪問二叉樹int u = q.front();             //讀隊(duì)頭，并輸出cout << t[u];q.pop();                       //隊(duì)頭處理完了，彈走if (t[ls(u)])  q.push(ls(u));  //左兒子進(jìn)隊(duì)列if (t[rs(u)])  q.push(rs(u));  //右兒子進(jìn)隊(duì)列}
}
int main(){t[1]='A';                                //第1層t[2]='B';           t[3]='C';            //第2層t[4]='D'; t[5]='E'; t[6]='F'; t[7]='G';  //第3層t[10]='H';          t[14]='I'; //第4層bfs(1);               //BFS訪問二叉樹，從根節(jié)點(diǎn)1開始。輸出：ABCDEFGHIcout<<"\n";bfs(3);               //BFS訪問二叉樹的子樹，從子節(jié)點(diǎn)3開始。輸出：CFGIreturn 0;
}

Java代碼

import java.util.*;
public class Main {private static final int N = 100;private static char[] t = new char[N];           //簡(jiǎn)單地用一個(gè)數(shù)組定義二叉樹private static int ls(int p) {return p<<1;}       //定位左孩子，也可以寫成 p*2private static int rs(int p) {return (p<<1) | 1;} //定位右孩子，也可以寫成 p*2+1private static void bfs(int root) {Queue<Integer> queue = new LinkedList<>();    //定義隊(duì)列queue.add(root);                              //第一個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列while (!queue.isEmpty()) {                    //用BFS訪問二叉樹int u = queue.peek();                     //讀隊(duì)頭，并輸出System.out.print(t[u]);queue.poll();                             //隊(duì)頭處理完了，彈走if (t[ls(u)] != '\0')   queue.add(ls(u));   //左兒子進(jìn)隊(duì)列      if (t[rs(u)] != '\0')   queue.add(rs(u));   //右兒子進(jìn)隊(duì)列     }}public static void main(String[] args) {t[1] = 'A';                                            //第1層t[2] = 'B';   t[3] = 'C';                              //第2層t[4] = 'D';   t[5] = 'E';   t[6] = 'F';  t[7] = 'G';   //第3層t[10] = 'H';  t[14] = 'I';                             //第4層bfs(1);              //BFS訪問二叉樹，從根節(jié)點(diǎn)1開始。輸出：ABCDEFGHISystem.out.println();bfs(3);              //BFS訪問二叉樹的子樹，從子節(jié)點(diǎn)3開始。輸出：CFGI}
}

Python代碼

from collections import deque
N = 100
t = [''] * N                            # 簡(jiǎn)單地用一個(gè)數(shù)組定義二叉樹
def ls(p):  return p << 1               # 定位左孩子，也可以寫成 p*2
def rs(p):  return (p << 1) | 1         # 定位右孩子，也可以寫成 p*2+1
def bfs(root):       q = deque()                         # 定義隊(duì)列q.append(root)                      # 第一個(gè)節(jié)點(diǎn)進(jìn)入隊(duì)列while q:                            # 用BFS訪問二叉樹u = q.popleft()                 # 讀隊(duì)頭，并彈走print(t[u], end='')             # 輸出隊(duì)頭if t[ls(u)]:  q.append(ls(u))   # 左兒子進(jìn)隊(duì)列   if t[rs(u)]:  q.append(rs(u))   # 右兒子進(jìn)隊(duì)列   
t[1] = 'A'                              # 第1層
t[2] = 'B'; t[3] = 'C'                  # 第2層
t[4] = 'D'; t[5] = 'E'; t[6] = 'F'; t[7] = 'G'         # 第3層
t[10] = 'H';t[14] = 'I'                 # 第4層
bfs(1)         # BFS訪問二叉樹，從根節(jié)點(diǎn)1開始。輸出：ABCDEFGHI
print()
bfs(3)         # BFS訪問二叉樹的子樹，從子節(jié)點(diǎn)3開始。輸出：CFGI

2. BFS與最短路徑

??求最短路徑是BFS最常見的應(yīng)用。
??BFS本質(zhì)上就是一個(gè)最短路徑算法，因?yàn)樗蛇M(jìn)及遠(yuǎn)訪問節(jié)點(diǎn)，先訪問到的節(jié)點(diǎn)，肯定比后訪問到的節(jié)點(diǎn)更近。某個(gè)節(jié)點(diǎn)第一次被訪問到的時(shí)候，必定是從最短路徑走過來的。從起點(diǎn)出發(fā)，同一層的節(jié)點(diǎn)，到起點(diǎn)的距離都相等。
??不過，BFS求最短路有個(gè)前提：任意兩個(gè)鄰居節(jié)點(diǎn)的邊長都相等，把兩個(gè)鄰居節(jié)點(diǎn)之間的邊長距離稱為“一跳”。只有所有邊長都相等，才能用BFS的逐層遞進(jìn)來求得最短路。兩個(gè)節(jié)點(diǎn)之間的路徑長度，等于這條路徑上的邊長個(gè)數(shù)。在這種場(chǎng)景下，BFS是最優(yōu)的最短路算法，它的計(jì)算復(fù)雜度只有O(n+m)，n是節(jié)點(diǎn)數(shù)，m是邊數(shù)。如果邊長都不等，就不能用BFS求最短路了，路徑長度也不能簡(jiǎn)單地用邊長個(gè)數(shù)來統(tǒng)計(jì)。
??下圖中，A到B、C、D的最短路長度都是1跳，A到E、F、G、H的最短路都是2跳。

??用BFS求最短路路徑的題目一般有兩個(gè)目標(biāo)：
??（1）最短路徑的長度。答案唯一，路徑長度就是路徑經(jīng)過的邊長數(shù)量。
??（2）最短路徑具體經(jīng)過哪些節(jié)點(diǎn)。由于最短路徑可能有多條，所以一般不用輸出最短路徑。如果要輸出，一般是輸出字典序最小的那條路徑。例如上圖中，A到F的最短路有兩條：A-B-F、A-C-F，字典序最小的是A-B-F。
??BFS最短路徑的常用的場(chǎng)景是網(wǎng)格圖，下面給出一道例題，用這道例題說明如何計(jì)算最短路、如何輸出路徑。

2.1 計(jì)算最短路的長度

例題：馬的遍歷

??馬走日，從一個(gè)坐標(biāo)點(diǎn)出發(fā)，下一步有8種走法。第4、5行用dx[]、dy[]定義下一步的8個(gè)方向。設(shè)左上角的坐標(biāo)是(1,1)，右下角坐標(biāo)是(n,m)。
??代碼的主體部分是標(biāo)準(zhǔn)的BFS，讓每個(gè)點(diǎn)進(jìn)出隊(duì)列。注意如何用隊(duì)列處理坐標(biāo)。第24行定義隊(duì)列，隊(duì)列元素是坐標(biāo)struct node。
??用dis[][]記錄最短路徑長度，dis[x][y]是從起點(diǎn)s到(x,y)的最短路徑長度。第35行，每擴(kuò)散一層，路徑長度就加1。
C++代碼：

#include <bits/stdc++.h>
using namespace std;
struct node{int x,y;};                    //定義坐標(biāo)。左上角(1,1)，右下角(n,m)
const int dx[8]={2,1,-1,-2,-2,-1, 1, 2};  //8個(gè)方向，按順時(shí)針
const int dy[8]={1,2, 2, 1,-1,-2,-2,-1};
int dis[500][500];                        //dis[x][y]: 起點(diǎn)到(x,y)的最短距離長度
int vis[500][500];                        //vis[x][y]=1: 已算出起點(diǎn)到坐標(biāo)(x,y)的最短路
node pre[500][500];                       //pre[x][y]:坐標(biāo)(x,y)的前驅(qū)點(diǎn)
void print_path(node s, node t){          //打印路徑：從起點(diǎn)s到終點(diǎn)tif(t.x==s.x && t.y==s.y) {           //遞歸到了起點(diǎn)printf("(%d,%d)->",s.x,s.y);      //打印起點(diǎn)，返回return;}node p;p.x = pre[t.x][t.y].x;    p.y = pre[t.x][t.y].y;print_path(s,p);                     //先遞歸回到起點(diǎn)printf("(%d,%d)->",t.x,t.y);         //在回溯過程中打印，最后打的是終點(diǎn)
}
int main(){int n,m; node s;   cin>>n>>m>>s.x>>s.y;memset(dis,-1,sizeof(dis));dis[s.x][s.y]=0;                      //起點(diǎn)到自己的距離是0vis[s.x][s.y]=1;queue<node> q;q.push(s);                            //起點(diǎn)進(jìn)隊(duì)while(!q.empty()){node now = q.front();q.pop();                          //取隊(duì)首并出隊(duì)for(int i=0;i<8;i++) {            //下一步可以走8個(gè)方向node next;next.x=now.x+dx[i],next.y=now.y+dy[i];if(next.x<1||next.x>n||next.y<1||next.y>m||vis[next.x][next.y])continue;                   //出界或已經(jīng)走過vis[next.x][next.y]=1;         //標(biāo)記為已找到最短路dis[next.x][next.y]=dis[now.x][now.y]+1;  //計(jì)算最短路長度pre[next.x][next.y] = now;    //記錄點(diǎn)next的前驅(qū)是nowq.push(next);                 //進(jìn)隊(duì)列}}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++)printf("%-5d",dis[i][j]);printf("\n");}// node test; test.x=3; test.y=3;  //測(cè)試路徑打印，樣例輸入：3 3 1 1，終點(diǎn)(3,3)// print_path(s,test);           //輸出路徑：(1,1)->(3,2)->(1,3)->(2,1)->(3,3)->return 0;
}

2.2 輸出完整的最短路徑

??本題沒有要求打印出具體的路徑，不過為了演示如何打印路徑，代碼中加入了函數(shù)print_path(s,t)，打印從起點(diǎn)s到終點(diǎn)t的完整路徑。第47行打印起點(diǎn)s=(1,1)，終點(diǎn)t=(3,3)的完整路徑：(1,1)->(3,2)->(1,3)->(2,1)->(3,3)。如下圖虛線箭頭所示。

??如何記錄一條路徑？在圖上從一個(gè)起點(diǎn)s出發(fā)做一次BFS，可以求s到其他所有點(diǎn)的最短路。為了記錄路徑，最簡(jiǎn)單的方法是每走到一個(gè)點(diǎn)i，就在i上把從起點(diǎn)s到i經(jīng)過的所有點(diǎn)都記下來。例如上圖，從(1,1)出發(fā)，下一步可以走到(3,2)，就在(3,2)上記錄”(1,1)->(3,2)”；再走一步可以到(1,3)，就在(1,3)上接著記錄“(1,1)->(3,2)->(1,3)”；再走一步到(2,1)，就在(2,1)上記錄“(1,1)->(3,2)->(1,3)->(2,1)”。這樣做編程簡(jiǎn)單，但是浪費(fèi)空間，因?yàn)槊總€(gè)點(diǎn)上都要記錄從頭到尾的完整路徑。
??《算法競(jìng)賽》123頁“3.4 BFS與最短路徑”介紹了這兩種路徑記錄方法：簡(jiǎn)單方法、標(biāo)準(zhǔn)方法。
??標(biāo)準(zhǔn)的路徑記錄方法是：只在點(diǎn)i上記錄前驅(qū)點(diǎn)，也就是從哪個(gè)點(diǎn)走到i的。例如點(diǎn)(1,3)，記錄它的前驅(qū)點(diǎn)是(3,2)，(3,2)記錄它的前驅(qū)點(diǎn)是(1,1)。當(dāng)需要輸出起點(diǎn)(1,1)到(1,3)的完整路徑時(shí)，只需要從(3,2)倒查回去，就能得到完整路徑了。這樣做非常節(jié)省空間，一個(gè)點(diǎn)上只需要記錄前一個(gè)點(diǎn)就行了。
??為什么不在點(diǎn)i上記錄它的下一個(gè)點(diǎn)？請(qǐng)讀者自己思考。
??代碼第8行用node pre[][]記錄路徑，pre[x][y]記錄了坐標(biāo)(x,y)的前驅(qū)點(diǎn)。按照pre[][]的記錄倒查路徑上每個(gè)點(diǎn)的前一個(gè)點(diǎn)，一直查到起點(diǎn)，就得到了完整路徑。例如上圖，終點(diǎn)為(3,3)，pre[3][3]是它的上一個(gè)點(diǎn)(2,1)；(2,1)的pre[2][1]是它的上一個(gè)點(diǎn)(1,3)；(1,3)的上一個(gè)點(diǎn)是(3,2)；(3,2)的上一個(gè)點(diǎn)是(1,1)，回到了起點(diǎn)。
??print_path()打印路徑，它是一個(gè)遞歸函數(shù)，從終點(diǎn)開始倒查pre[][]，一直遞歸到起點(diǎn)，然后再回溯回終點(diǎn)。在回溯的過程中從起點(diǎn)開始打印路徑上的點(diǎn)，就得到了從起點(diǎn)到終點(diǎn)的正序路徑。
另外，從起點(diǎn)s到終點(diǎn)t可能有多條最短路徑，上面的代碼只記錄了按順時(shí)針的優(yōu)先順序找到的第一條最短路徑。第4、5行的dx[]、dy[]按順時(shí)針定義了8個(gè)方向，然后在第29行遍歷鄰居時(shí)，也是按dx[]、dy[]的順序，那么得到的最短路徑就是按順時(shí)針的。
??Java代碼：

import java.util.*;
class Main {static class Node {              //定義坐標(biāo)。左上角(1,1)，右下角(n,m)int x, y;Node(int x, int y) {this.x = x;this.y = y;}}public static void printPath(Node s, Node t, Node[][] pre){ //打印路徑:起點(diǎn)s終點(diǎn)tif (t.x == s.x && t.y == s.y) {                       //遞歸到了起點(diǎn)System.out.print("(" + s.x + "," + s.y + ")->");  //打印起點(diǎn)，然會(huì)回溯return;}Node p = pre[t.x][t.y];printPath(s, p, pre);                             //先遞歸回到起點(diǎn)System.out.print("(" + t.x + "," + t.y + ")->");  //回溯打印，最后打的是終點(diǎn)}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();Node s = new Node(scanner.nextInt(), scanner.nextInt());int[][] dis = new int[n+1][m+1];   //dis[x][y]:起點(diǎn)到(x,y)的最短距離長度int[][] vis = new int[n+1][m+1];   //vis[x][y]=1:已算出起點(diǎn)到坐標(biāo)(x,y)的最短路Node[][] pre = new Node[n + 1][m + 1];   //pre[x][y]:坐標(biāo)(x,y)的前驅(qū)點(diǎn)int[] dx = {2, 1, -1, -2, -2, -1, 1, 2}; //8個(gè)方向，按順時(shí)針int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)dis[i][j] = -1;dis[s.x][s.y] = 0;                    //起點(diǎn)到自己的距離是0vis[s.x][s.y] = 1;Queue<Node> queue = new LinkedList<>();queue.add(s);                         //起點(diǎn)進(jìn)隊(duì)while (!queue.isEmpty()) {Node now = queue.poll();          //取隊(duì)首并出隊(duì)for (int i = 0; i < 8; i++) {int nx = now.x + dx[i];int ny = now.y + dy[i];if (nx < 1 || nx > n || ny < 1 || ny > m || vis[nx][ny] == 1) continue;                  //出界或已經(jīng)走過vis[nx][ny] = 1;               //標(biāo)記為已找到最短路dis[nx][ny] = dis[now.x][now.y] + 1;      //計(jì)算最短路長度pre[nx][ny] = now;             //記錄點(diǎn)next的前驅(qū)是nowqueue.add(new Node(nx, ny));//進(jìn)隊(duì)列}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) System.out.printf("%-5d", dis[i][j]);            System.out.println();}// Node test = new Node(3, 3);   //測(cè)試路徑打印，樣例輸入：3 3 1 1，終點(diǎn)(3,3)// printPath(s, test, pre);    //輸出路徑：(1,1)->(3,2)->(1,3)->(2,1)->(3,3)->}
}

??Python代碼

from collections import deque
dx = [2, 1, -1, -2, -2, -1, 1, 2]         #8個(gè)方向，按順時(shí)針
dy = [1, 2, 2, 1, -1, -2, -2, -1]
class Node:                               #定義坐標(biāo)。左上角(1,1)，右下角(n,m)def __init__(self, x, y):self.x = xself.y = y
def print_path(s, t, pre):                #打印路徑：從起點(diǎn)s到終點(diǎn)tif t.x == s.x and t.y == s.y:         #遞歸到了起點(diǎn)print(f"({s.x},{s.y})->", end="") #打印起點(diǎn)，返回returnp = pre[t.x][t.y] print_path(s, p, pre)                 #先遞歸回到起點(diǎn)print(f"({t.x},{t.y})->", end="")     #在回溯過程中打印，最后打的是終點(diǎn)
def main():n, m,u,v = map(int, input().split())s = Node(u,v)dis = [[-1] * (m+1) for _ in range(n+1)] #dis[x][y]: 起點(diǎn)到(x,y)的最短距離長度vis = [[0] * (m+1) for _ in range(n+1)]  #vis[x][y]=1: 已算出起點(diǎn)到(x,y)的最短路pre = [[None] * (m+1) for _ in range(n+1)]  #pre[x][y]: 坐標(biāo)(x,y)的前驅(qū)點(diǎn)dis[s.x][s.y] = 0                           #起點(diǎn)到自己的距離是0vis[s.x][s.y] = 1q = deque([s])                              #起點(diǎn)進(jìn)隊(duì)while q: now = q.popleft()                       #取隊(duì)首并出隊(duì)for i in range(8):                      #下一步可以走8個(gè)方向nx, ny = now.x + dx[i], now.y + dy[i]if nx<1 or nx>n or ny < 1 or ny > m or vis[nx][ny]:continue                        #出界或已經(jīng)走過vis[nx][ny] = 1                     #標(biāo)記為已找到最短路dis[nx][ny] = dis[now.x][now.y] + 1    #計(jì)算最短路長度pre[nx][ny] = now                      #記錄點(diǎn)(nx,ny)的前驅(qū)是nowq.append(Node(nx, ny))                 #進(jìn)隊(duì)列for i in range(1, n + 1):for j in range(1, m + 1):print(f"{dis[i][j]:-5d}", end="")print()    #test = Node(3, 3)                 #測(cè)試路徑打印，樣例輸入：3 3 1 1，終點(diǎn)(3,3)#print_path(s, test, pre)          #輸出路徑：(1,1)->(3,2)->(1,3)->(2,1)->(3,3)->
if __name__ == "__main__":main()

3. BFS與判重

??BFS的題目往往需要“判重”。BFS的原理是逐層擴(kuò)展，把擴(kuò)展出的下一層點(diǎn)（或稱為狀態(tài)）放進(jìn)隊(duì)列中。
??在任意時(shí)刻，隊(duì)列中只包含相鄰兩層的點(diǎn)。只有兩層，看起來似乎不多，但是很多情況下是個(gè)極大的數(shù)字。例如一棵滿二叉樹，第25層的點(diǎn)就有225≈3000萬個(gè)，隊(duì)列放不下。
??不過在很多情況下，其實(shí)狀態(tài)的總數(shù)量并不多，在層層擴(kuò)展過程中，很多狀態(tài)是重復(fù)的，沒有必要重新放進(jìn)隊(duì)列。這產(chǎn)生了判重的需求。
??用下面的題目說明判重的原理和編程方法。

例題：九宮重排

??題目求從初態(tài)到終態(tài)的最少步數(shù)，是典型的BFS最短路路徑問題。
??讓卡片移動(dòng)到空格比較麻煩，改為讓空格上下左右移動(dòng)，就簡(jiǎn)單多了?？崭竦拿恳徊揭苿?dòng)，可能有2、3、4種新局面，如果按3種算，移動(dòng)到第15步，就有315>1千萬種局面，顯然隊(duì)列放不下。不過，其實(shí)局面總數(shù)僅有9!=362880種，隊(duì)列放得下，只要判重，不讓重復(fù)的局面進(jìn)入隊(duì)列即可。

3.1 C++判重

??判重可以用STL map或set。（1）map判重。map是STL容器，存放鍵值對(duì)。鍵有唯一性，鍵和值有一一對(duì)應(yīng)關(guān)系。由于每個(gè)鍵是獨(dú)一無二的，可以用來判重。map的基本用法見下面的例子。

#include <bits/stdc++.h>
using namespace std;
int main(){map<string,int> mp{{"tom",78},{"john",92},{"rose",83}}; //三個(gè)鍵值對(duì)cout << mp["tom"]<<"\n";                //輸出  78cout << mp.count("tom")<<"\n";          //檢查map中是否有"tom"。輸出  1mp["white"]=100;                        //加入新鍵值對(duì)，鍵是"white"，值是100cout << mp["white"]<<"\n";              //輸出 100cout << mp.count("sam")<<"\n";          //查不到鍵，輸出 0map<int, int> mp2{{2301,89},{2302,98}}; cout << mp2[2301]<<"\n";                //輸出 89map<int, string> mp3{{301,"dog"},{232,"pig"}};cout << mp3[232]<<"\n";                 //輸出 pigreturn 0;
}

??map容器中提供了count()用于統(tǒng)計(jì)鍵的個(gè)數(shù)，有鍵返回1，沒有鍵返回0。count()可以用來判重：若某個(gè)鍵的count()等于1，說明這個(gè)鍵已經(jīng)在map中，不用再放進(jìn)map。
??下面給出本題的C++代碼。第22行判重，判斷局面tmp是否曾經(jīng)處理過，第23行把新局面tmp放進(jìn)map。

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1,  0};  //上下左右四個(gè)方向
int dy[] = { 0, 1, 0, -1};
map <string,int> mp;
int bfs(string s1,string s2){queue<string>q;q.push(s1);mp[s1]=0;           //mp[s1]=0表示s1到s1的步數(shù)是0。另外：mp.count(s1)=1while(q.size()){string ss = q.front();q.pop();int dist = mp[ss];       //從s1到ss的移動(dòng)步數(shù)if(ss==s2)  return dist; //到達(dá)終點(diǎn)，返回步數(shù)int k=ss.find('.');      //句點(diǎn)的位置int x=k/3,y=k%3;         //句點(diǎn)坐標(biāo)：第x行、第y列for(int i=0;i<4;i++){int nx=x+dx[i], ny=y+dy[i];  //讓句點(diǎn)上下左右移動(dòng)if(nx<0 || ny<0 || nx>2 || ny>2) continue;  //越界string tmp=ss;swap(tmp[k],tmp[nx*3+ny]);  //移動(dòng)if(mp.count(tmp)==0){       //判重，如果tmp曾經(jīng)處理過，就不再處理mp[tmp] = dist+1; //把tmp放進(jìn)map，并賦值。mp[tmp]等于s1到tmp的步數(shù)q.push(tmp);}}}return -1;                      //沒有找到終態(tài)局面，返回-1
}
int main(){string s1,s2;   cin>>s1>>s2;    //初態(tài)局面s1，終態(tài)局面s2cout<<bfs(s1,s2);return 0;
}

??（2）set判重。set是STL的常用容器，set中的元素是有序的且具有唯一性，利用這個(gè)特性，set常用來判重。set的基本用法見下面的例子。

#include <bits/stdc++.h>
using namespace std;
int main() {set<string>st{"111","222","33"};        // 定義 set，插入初值if(st.count("111")) cout <<1;           //有"111"，輸出   1else cout <<-1;cout<<"\n";if(st.count("44")) cout <<4;else cout <<-4;                         //無"44"，輸出   -4cout <<"\n";st.insert("44");                        //插入"44"if(st.count("44")) cout <<4;            //有"44"，輸出   4return 0;
}

??本題用set判重的代碼：

#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1,  0};    //上下左右四個(gè)方向
int dy[] = { 0, 1, 0, -1};
struct node{node(string ss, int tt){s=ss, t=tt;}string s;     //局面int t;        //到這個(gè)局面的步數(shù)
};
set <string> st;   //用set st判重
int bfs(string s1,string s2){queue<node>q;q.push(node(s1,0));st.insert(s1);while(q.size()){node now = q.front();q.pop();string ss = now.s;int dist = now.t;         //從s1到ss的移動(dòng)步數(shù)if(ss==s2)  return dist;  //到達(dá)終點(diǎn)，返回步數(shù)int k=ss.find('.');       //句點(diǎn)的位置int x=k/3,y=k%3;          //句點(diǎn)坐標(biāo)：第x行、第y列for(int i=0;i<4;i++){int nx=x+dx[i], ny=y+dy[i];          //讓句點(diǎn)上下左右移動(dòng)if(nx<0 || ny<0 || nx>2 || ny>2) continue;  //越界string tmp=ss;swap(tmp[k],tmp[nx*3+ny]);  //移動(dòng)if(st.count(tmp)==0){       //判重，如果tmp曾經(jīng)處理過，就不再處理st.insert(tmp);q.push(node(tmp,dist+1));}}}return -1;                      //沒有找到終態(tài)局面，返回-1
}
int main(){string s1,s2;   cin>>s1>>s2;    //初態(tài)局面s1，終態(tài)局面s2cout<<bfs(s1,s2);return 0;
}

3.2 Java判重

??（1）用map判重

import java.util.*;
public class Main {static int[] dx = {-1, 0, 1, 0};  // 上下左右四個(gè)方向static int[] dy = {0, 1, 0, -1};static Map<String, Integer> mp;public static int bfs(String s1, String s2) {Queue<String> q = new LinkedList<>();q.add(s1);mp.put(s1, 0);                // 0表示s1到s1的步數(shù)是0while (!q.isEmpty()) {String ss = q.poll();int dist = mp.get(ss);  // 從s1到ss的移動(dòng)步數(shù)if (ss.equals(s2)) return dist;  // 到達(dá)終點(diǎn)，返回步數(shù)int k = ss.indexOf('.');  // 句點(diǎn)的位置int x = k / 3, y = k % 3;  // 句點(diǎn)坐標(biāo)：第x行、第y列for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];  // 讓句點(diǎn)上下左右移動(dòng)if (nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;  // 越界StringBuilder tmp = new StringBuilder(ss);tmp.setCharAt(k, tmp.charAt(nx * 3 + ny));  // 移動(dòng)tmp.setCharAt(nx * 3 + ny, '.');if (!mp.containsKey(tmp.toString())) {//判重，如果tmp處理過，就不再處理mp.put(tmp.toString(), dist + 1); //把tmp放進(jìn)map，并賦值為步數(shù)q.add(tmp.toString());}}}return -1;  // 沒有找到終態(tài)局面，返回-1}public static void main(String[] args) {mp = new HashMap<>();Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();System.out.println(bfs(s1, s2));}
}

??（2）用set判重

import java.util.*;
public class Main {static int[] dx = {-1, 0, 1, 0};  // 上下左右四個(gè)方向static int[] dy = {0, 1, 0, -1};static Set<String> st;static class Node {String s;  // 局面int t;     // 到這個(gè)局面的步數(shù)public Node(String ss, int tt) {s = ss;t = tt;}}public static int bfs(String s1, String s2) {Queue<Node> q = new LinkedList<>();q.add(new Node(s1, 0));st.add(s1);while (!q.isEmpty()) {Node now = q.poll();String ss = now.s;int dist = now.t;  // 從s1到ss的移動(dòng)步數(shù)if (ss.equals(s2)) return dist;  // 到達(dá)終點(diǎn)，返回步數(shù)int k = ss.indexOf('.');  // 句點(diǎn)的位置int x = k / 3, y = k % 3;  // 句點(diǎn)坐標(biāo)：第x行、第y列for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];  // 讓句點(diǎn)上下左右移動(dòng)if (nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;  // 越界StringBuilder tmp = new StringBuilder(ss);tmp.setCharAt(k, tmp.charAt(nx * 3 + ny));  // 移動(dòng)tmp.setCharAt(nx * 3 + ny, '.');if (!st.contains(tmp.toString())) {//判重，如果tmp處理過，就不再處理st.add(tmp.toString());q.add(new Node(tmp.toString(), dist + 1));}}}return -1;  // 沒有找到終態(tài)局面，返回-1}public static void main(String[] args) {st = new HashSet<>();Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();System.out.println(bfs(s1, s2));}
}

3.3 Python判重

??（1）用set判重

from collections import deque
dx = [-1, 0, 1, 0]  # 上下左右四個(gè)方向
dy = [0, 1, 0, -1]
class Node:def __init__(self, s, t):self.s = s  # 局面self.t = t  # 到這個(gè)局面的步數(shù)
def bfs(s1, s2):q = deque()q.append(Node(s1, 0))st = set()st.add(s1)while q:now = q.popleft()ss = now.sdist = now.t        # 從s1到ss的移動(dòng)步數(shù)if ss == s2:  return dist  # 到達(dá)終點(diǎn)，返回步數(shù)k = ss.index('.')x = k // 3y = k % 3for i in range(4):nx = x + dx[i]ny = y + dy[i]if nx < 0 or ny < 0 or nx > 2 or ny > 2:   continue  # 越界tmp = list(ss)tmp[k], tmp[nx * 3 + ny] = tmp[nx * 3 + ny], tmp[k]  # 移動(dòng)tmp = ''.join(tmp)if tmp not in st:  # 判重，如果tmp曾經(jīng)處理過，就不再處理st.add(tmp)q.append(Node(tmp, dist + 1))return -1  # 沒有找到終態(tài)局面，返回-1
s1 = input()  # 初態(tài)局面s1
s2 = input()  # 終態(tài)局面s2
print(bfs(s1, s2))

??（2）用字典判重

from collections import deque
dx = [-1, 0, 1, 0]          # 上下左右四個(gè)方向
dy = [0, 1, 0, -1]
def bfs(s1, s2):q = deque()q.append(s1)mp = {s1: 0}           # 定義字典。mp[s1]=0表示s1到s1的步數(shù)是0 while q:ss = q.popleft()dist = mp[ss]      # 從s1到ss的移動(dòng)步數(shù)if ss == s2:   return dist    # 到達(dá)終點(diǎn)，返回步數(shù)k = ss.find('.')x = k // 3y = k % 3for i in range(4):nx = x + dx[i]ny = y + dy[i]if nx < 0 or ny < 0 or nx > 2 or ny > 2:  continue   # 越界tmp = list(ss)tmp[k], tmp[nx * 3 + ny] = tmp[nx * 3 + ny], tmp[k]  # 移動(dòng)tmp = ''.join(tmp)if tmp not in mp:  # 判重，如果tmp曾經(jīng)處理過，就不再處理mp[tmp] = dist + 1  # 把tmp放進(jìn)map，并賦值。mp[tmp]等于s1到tmp的步數(shù)q.append(tmp)return -1  # 沒有找到終態(tài)局面，返回-1
s1 = input()  # 初態(tài)局面s1
s2 = input()  # 終態(tài)局面s2
print(bfs(s1, s2))

習(xí)題：
洛谷搜索提單：https://www.luogu.com.cn/training/112#problems