目前做到的主要3类bfs题型：

(1).基础类型：迷宫，各种乱跳，扩散，分析转换，模拟

此类基本通用的bfs都可做

(2).”康托展开”类型：八数码

(3).”二进制”状态展开类型：棋盘游戏

！！！最后给一道提高题：

(1).2维迷宫题型

传送门：https://www.acwing.com/problem/content/1101/

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int>PII;
typedef pair<PII,int>PIII;
const int N = 305;
char g[N][N];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int n, m;
int x, y;

int bfs(){
    queue<PIII>q;
    q.push({{x, y}, 0});
    g[x][y] = '#';
    while(q.size()){
        PIII st = q.front();
        q.pop();
        PII u = st.first;
        int dist = st.second;
        for(int i = 0; i < 4; i ++ ){
            int a = dx[i] + u.first, b = dy[i] + u.second;
            if(a >= 0 && b >= 0 && a < n && b < m && g[a][b] != '#'){
                q.push({{a, b}, dist + 1});
                if(g[a][b] == '*')  return dist + 1;
                g[a][b] = '#';
            }
        }
    }
    return -1;
}

int main(){
    while(cin>>n>>m, n && m){
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ ){
                cin>>g[i][j];
                if(g[i][j] == '@')  x = i, y = j;
            }
        cout<<bfs()<<'\n';
    }
    return 0;
}

(1).3维迷宫题型

传送门：https://www.acwing.com/problem/content/1098/

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int N = 105;
//这3个偏移量对应：北,东,南,西,上,下移动一个单元
int dx[] = {-1, 0, 1, 0, 0, 0}; 
int dy[] = {0, 1, 0, -1, 0, 0};
int dz[] = {0, 0, 0, 0, 1, -1};

char g[N][N][N];    //一维表示第几层，二维和三维表示行数和列数
int h, n, m;    //  h表示几层,n和m分别表示每一层的行数和列数

struct Node{
    int x, y, z;    //定义一个结构体记录每个点的三维坐标
};

Node start; 

typedef pair<Node,int>PNI;  //定义一个结构体和int型的二元组

int bfs(int cx, int cy, int cz){
    g[cz][cx][cy] = '#';    //将'S'初始点记录'#'表示走过即无法走了
    queue<PNI>q;    //定义一个<{{三维坐标},到达该点所需的分钟数}>的队列
    q.push({{cx, cy, cz}, 0});  //将'S'点加入队列
    while(q.size()){
        auto u = q.front();
        q.pop();
        for(int i = 0; i < 6; i ++ ){
            auto jgt = u.first; //将二元组第一个类型结构体的值取出
            int x = jgt.x, y = jgt.y, z = jgt.z, dist = u.second;
            int a = x + dx[i], b = y + dy[i], c = z + dz[i];
            if(a >= 0 && b >= 0 && c >= 0 && a < n && b < m && c < h && g[c][a][b] != '#'){
                q.push({{a, b, c}, dist + 1});
                if(g[c][a][b] == 'E')   return dist + 1;    //如果找到了就退出
                g[c][a][b] = '#';   //如果走过了就要记录
            }
        }
    }
    return -1;
}

int main(){
    while(cin>>h>>n>>m, h && n && m){
        string s;
        for(int i = 0;i < h; i ++ ){    //表示层数
            for(int j = 0; j < n; j ++ ){   //表示行数
                cin>>g[i][j];
                for(int k = 0; k < m; k ++ )    
                    if(g[i][j][k] == 'S')   
                        start.x = j, start.y = k, start.z = i;      //记录'S'的位置
                }
            getline(cin, s);    //读入空行
        }
        int val = bfs(start.x, start.y, start.z);
        if(val != -1)   printf("Escaped in %d minute(s).\n", val); //能走出地牢
        else    printf("Trapped!\n");   //不能走出地牢
    }
    return 0;
}

(1).迷宫路径记录

传送门：http://poj.org/problem?id=3984

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio> 

using namespace std;

const int N = 10;
typedef pair<int,int>PII;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
PII suc[N][N];
char g[N][N];

void bfs(){
    queue<PII>q;
    q.push({4, 4});
    g[4][4] = '1';
    while(q.size()){
        PII u = q.front();
        q.pop();
        for(int i = 0; i < 4; i ++ ){
            int a = u.first + dx[i], b = u.second + dy[i];
            if(a >= 0 && b >= 0 && a < 5 && b < 5 && g[a][b] == '0'){
                g[a][b] = '1';
                q.push({a, b});
                suc[a][b] = u;
                if(!a && !b)    return ;
            }
        }
    }
}

int main(){
    for(int i = 0; i < 5; i ++ )
        for(int j = 0; j < 5; j ++ )
            cin>>g[i][j];
    bfs();
    int x = 0, y = 0;
    while(true){
        printf("(%d, %d)\n", x, y);
        int a = suc[x][y].first, b = suc[x][y].second;
        x = a, y = b;
        if(x == 4 && y == 4)    break;
    }
    printf("(4, 4)");
    return 0;
}

(1)乱跳：

传送门：https://www.acwing.com/problem/content/190/

#include<iostream>
#include<queue>

using namespace std;

const int N = 155;

struct mxd{
    int x, y, ans;
};
int n, m;
char g[N][N];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
queue<mxd>q;

void bfs(){
    int res;
    while(q.size()){
        mxd u = q.front();
        q.pop();
        int x = u.x, y = u.y, ans = u.ans;
        for(int i = 0; i < 8; i ++ ){
            int a = dx[i] + x, b = dy[i] + y;
            if(a >= 0 && b >= 0 && a < n && b < m && g[a][b] != '*'){
                res = ans + 1;
                q.push({a, b, res});
                if(g[a][b] == 'H'){
                    cout<< res;
                    return;
                }
                g[a][b] = '*';
            }
        }
    }
}

int main(){
    cin>>m>>n;
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ ){
            cin>>g[i][j];
            if(g[i][j] == 'K')  q.push({i, j, 0}), g[i][j] = '*';
        }
    bfs();
    return 0;
}

(1)乱跳

传送门：https://www.acwing.com/problem/content/1104/

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int>PII;
typedef pair<PII,int>PIII;
const int N = 305;

bool g[N][N];
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
int n;
int sx, sy, ex, ey;

int bfs(){
    memset(g, false, sizeof g);
    queue<PIII>q;
    q.push({{sx, sy}, 0});
    g[sx][sy] = true;
    while(q.size()){
        PIII st = q.front();
        q.pop();
        PII u = st.first;
        int dist = st.second;
        for(int i = 0; i < 8; i ++ ){
            int a = dx[i] + u.first, b = dy[i] + u.second;
            if(a >= 0 && b >= 0 && a < n && b < n && !g[a][b]){
                q.push({{a, b}, dist + 1});
                if(a == ex && b == ey)  return dist + 1;
                g[a][b] = true;
            }
        }
    }
    return 0;
}

int main(){
    int T;
    cin>>T;
    while(T -- ){
        cin>>n;
        cin>>sx>>sy>>ex>>ey;
        cout<<bfs()<<'\n';
    }
    return 0;
}

(1)扩散

传送门：https://www.acwing.com/problem/content/191/

#include<iostream>
#include<queue>

using namespace std;

const int N = 105;

int dx[] = {-1, 0, 1, -1, 1, -1, 0, 1}, dy[] = {1, 1, 1, 0, 0, -1, -1, -1};
int n, m, cx, cy;
char g[N][N];

struct Node{
    int x, y, t;
};

queue<Node>q;

void bfs(){
    int res;
    while(q.size()){
        Node u = q.front();
        q.pop();
        int x = u.x, y = u.y, t = u.t; 
        res = t;
        for(int i = 0; i < 8; i ++ ){
            int a = x + dx[i], b = y + dy[i];
            if(a >= 1 && b >= 1 && a <= m && b <= n && g[a][b] == '.'){
                q.push({a, b, t + 1});
                g[a][b] = '*';
            }
        }
    }
    cout<<res;
}

int main(){
    cin>>m>>n>>cx>>cy;
    for(int i = n; i; i -- )
        for(int j = 1; j <= m; j ++ )
            cin>>g[j][i];
    q.push({cx, cy, 0});
    g[cx][cy] = '*';
    bfs();
    return 0;
}

(1)分析转换

传送门：https://vjudge.net/problem/OpenJ_Bailian-2815

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

const int N = 105;
typedef pair<int,int>PII;

bool ne[N][N];
bool st[N][N];
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int n, m;
int mmax = 1;
int room;

void change(int x, int y, int val){
    x *= 2, y *= 2;
    ne[x][y] = 0;
    for(int i = 0; i < 4; i ++ ){
        int a = x + dx[i], b = y + dy[i];
        ne[a][b] = val >> i & 1;
    }
}

void bfs(){
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            int num = 0;
            while(1){
                queue<PII>q;
                if(st[i * 2][j * 2])    break;
                room ++;
                q.push({i * 2, j * 2});
                st[i * 2][j * 2] = true;
                while(q.size()){
                    PII u = q.front();
                    q.pop();
                    int x = u.first, y = u.second;
                    if(x % 2 == 0 && y % 2 == 0)    num ++;
                    for(int k = 0; k < 4; k ++ ){
                        int a = x + dx[k], b = y + dy[k];
                        if(!st[a][b] && !ne[a][b] && a >= 1 && a <= n * 2 + 1 && b >= 1 && b <= m * 2 + 1){
                            st[a][b] = true;
                            q.push({a, b});
                        }
                    }
                }
                mmax = max(mmax, num);
                break;
            }   
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(ne, 1, sizeof ne);
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            int x;
            cin>>x;
            change(i, j, x);
        }
    }
    bfs();
    cout<<room<<'\n'<<mmax;
    return 0;
}

(1)模拟：

传送门：https://www.acwing.com/problem/content/689/

#include<iostream>
#include<cstring>

using namespace std;

const int N = 305;

int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
char g[N][N];
int _0[N][N];
int T, n;

void dfs(int x, int y){
    _0[x][y] = -1;
    for(int i = 0; i < 8; i ++ ){
        int a = dx[i] + x, b = dy[i] + y;
        if(a >= 0 && b >= 0 && a < n && b < n && _0[a][b] != -1){
            if(!_0[a][b])   _0[a][b] = -1, dfs(a, b);
            _0[a][b] = -1;
        }
    }
}

int main(){
    cin>>T;
    for(int q = 1; q <= T; q ++ ){
        int res = 0;
        cin>>n;
        for(int i = 0; i < n; i ++ )    cin>>g[i];
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ ){
                if(g[i][j] == '*')  _0[i][j] = -1;
                else{
                        _0[i][j] = 0;
                        for(int k = 0; k < 8; k ++ ){
                            int a = dx[k] + i, b = dy[k] + j;
                            if(a >= 0 && b >= 0 && a < n && b < n && g[a][b] == '*')
                                _0[i][j] ++;
                        }
                }
            }
        for(int i = 0; i < n; i ++ ){
            for(int j = 0; j < n; j ++ ){
                if(!_0[i][j]){
                    res ++;
                    dfs(i, j);
                }
            }
        }
        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < n; j ++ )
                if(_0[i][j] != -1)
                    res ++;
        printf("Case #%d: %d\n", q, res);
    }
    return 0;
}

康托展开：

(2).八数码：

传送门：https://www.acwing.com/problem/content/description/847/

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

using namespace std;

typedef pair<string,int>PSI;   //<情况，次数>
const int N = 10, M = 362880 + 5;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int fact[N];
bool st[M];
string s1;

int permutation_hash(string s){
    int ans = 0;
    for(int i = 0; i < 9; i ++ ){
        int cou = 0;
        for(int j = 0; j < i; j ++ ){
            if(s[j] > s[i]) cou ++;
        }
        ans += cou * fact[i];
    }
    return ans;
}

int bfs(){
    string s2 = "12345678x";
    int start = permutation_hash(s1);
    int end = permutation_hash(s2);
    st[start] = true;
    queue<PSI>q;
    q.push({s1, 0});
    while(q.size()){
        PSI u = q.front();
        if(permutation_hash(u.first) == end)   return u.second;
        q.pop();
        int pos = u.first.find('x');
        int x = pos / 3, y = pos % 3;
        for(int i = 0; i < 4; i ++ ){
            int a = dx[i] + x, b = dy[i] + y;
            if(a >= 0 && b >= 0 && a < 3 && b < 3){
                swap(u.first[pos], u.first[a * 3 + b]);
                int val = permutation_hash(u.first);
                if(!st[val])   q.push({u.first, u.second + 1});
                st[val] = true;
                swap(u.first[pos], u.first[a * 3 + b]);
            }
        }
    }
    return -1;
}

int main(){
    fact[0] = 1;
    for(int i = 1; i <= 9; i ++ ){
        char c;
        cin>>c;
        s1 += c;
        fact[i] = fact[i - 1] * i;
    }
    cout<<bfs();
    return 0;
}

二进制状态展开：

(3)棋盘游戏：

传送门：https://www.acwing.com/solution/content/11670/

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<string,int>PSI;    //<情况,次数>
const int N = 65536, M = 20;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool st[N]; // 每个状态是否被遍历过
string s1, s2;

char qr(){  //快读
    char c;
    do c = getchar();
    while(c == ' ' || c == '\n');
    return c;
}

int change2_10(string s){   //二进制转十进制
    int ans = 0;
    for(int i = 0; i < 16; i ++ ){
        int k = s[i] - '0';
        ans = ans * 2 + k;
    }
}

int bfs(){
    queue<PSI>q;
    q.push({s1, 0});    // 每个状态是否被遍历过
    int start = change2_10(s1);
    st[start] = true;   //初始状态计为true
    int end = change2_10(s2);   //记录结束状态
    while(q.size()){
        PSI u = q.front();
        q.pop();
        if(change2_10(u.first) == end)  return u.second;    // 每个状态是否被遍历过
        for(int i = 0; i < 16; i ++ ){
            if(u.first[i] == '1'){  // 每个状态是否被遍历过
                int x = i / 4, y = i % 4;   //从1维找到2维中黑棋1的位置
                for(int j = 0; j < 4; j ++ ){   
                    int a = dx[j] + x, b = dy[j] + y;
                    if(a >= 0 && b >= 0 && a < 4 && b < 4){
                        if(u.first[a * 4 + b] == '0'){  //黑棋跟黑棋交换没有意义
                            swap(u.first[a * 4 + b], u.first[i]);   //更新交换后黑棋的位置
                            int val = change2_10(u.first);
                            if(!st[val])    q.push({u.first, u.second + 1});//如果该t状态没有出现过，则压入队列中,次数+1
                            st[val] = true;
                            swap(u.first[a * 4 + b], u.first[i]);   //更新新的x的位置
                        }
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    for(int i = 0; i < 16; i ++ )    s1 += qr();
    for(int i = 0; i < 16; i ++ )    s2 += qr();
    cout<<bfs();
    return 0;
}

提高题：

传送门：https://ac.nowcoder.com/acm/contest/11218/E?&headNav=acm

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;

typedef pair<int,int>PII;
typedef pair<PII,PII>PIPI;  //{x,y,dist,hp}
const int N = 55;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
char g[N][N];
bool vis[N][N][N];
int n, m, h;

int bfs(){
    queue<PIPI>q;
    q.push({{0, 0}, {0, h}});
    while(q.size()){
        PIPI u = q.front();
        q.pop();
        PII l = u.first, r = u.second;
        int dist = r.first, hp = r.second;
        for(int i = 0; i < 4; i ++ ){
            int a = l.first + dx[i], b = l.second + dy[i];
            if(a >= 0 && b >= 0 && a < n && b < m && !vis[a][b][hp] && g[a][b] != '*'){
                vis[a][b][hp] = true;
                if(a == n - 1 && b == m - 1)    return dist + 1;
                if(g[a][b] == '.')  q.push({{a, b}, {dist + 1, hp}});
                else{
                    int rest_hp = hp - (g[a][b] - '0');
                    if(rest_hp > 0) q.push({{a, b}, {dist + 1, rest_hp}});
                }
            }
        }
    }
    return -1;
}

int main(){
    cin>>n>>m>>h;
    for(int i = 0; i < n; i ++ )    cin>>g[i];
    int val = bfs();
    cout<<val;
    return 0;
}