提高课搜索

Flood Fill 洪水漫灌算法：

多用于求一张矩阵图中连通块的大小、数量等。

多搭配bfs使用

1097.池塘计数

题意：求矩阵中共有多少片相连的”W”块

利用bfs逐层向外扩展的特性，当我们遍历到图中有一个W点，开始bfs，直到周围没有可扩展的w点。

走过的点需要标记 ，避免重复。

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 1e3 + 10;

typedef pair<int , int > PII;

char g[N][N];
bool st[N][N];
int n , m , res;
PII fi , now , ne;
int dx[8] = {-1 , 1 , 0 , 0 , -1 , 1 , -1 , 1};  //上下左右 左上 左下 右上 右下
int dy[8] = {0 , 0 , -1 , 1 , -1 , -1 , 1 , 1};

void bfs(int sx , int sy){

    queue<PII> Q;
    st[sx][sy] = 1;
    fi = {sx , sy};
    Q.push(fi);

    while(Q.size()){

        now = Q.front() , Q.pop();

        for(int i = 0; i < 8; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(g[nx][ny] == 'W' && !st[nx][ny]){
                st[nx][ny] = 1;
                ne = {nx , ny};
                Q.push(ne);

            }
        }
    }

}

int main(){

    cin >> n >> m;

    for(int i = 0; i < n; i ++) scanf("%s" , g[i]);

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(g[i][j] == 'W' && !st[i][j]) bfs(i , j) , res++;

    cout << res << endl;

    return 0;
}

1098.城堡问题

题意：求图内连通块个数及最大的大小

用flood fill 求解

处理输入的数字时注意，是这个点四周墙的分布情况：

​ 每个方块中墙的特征由数字 P 来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P 为该方块包含墙的数字之和。

由 1 2 4 8 想到这个数的二进制，我们判断这个方向有没有墙只需要 g[i , j] 右移 i位 ，判断这一位是不是1

是1代表有墙 ，走不通 ，0表示可以走

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int , int > PII;

const int N = 55;

int n , m , cnt , maxn;
int g[N][N];
bool st[N][N];
int dx[4] = {0 , -1 , 0 , 1} , dy[4] = {-1 , 0 , 1 , 0};//这里注意题目规定了左上右下的顺序
                                                        //1 2 4 8 西 北 东 南
PII fi , ne , now;

int bfs(int sx , int sy){

    int area = 0;
    queue<PII> Q;
    fi = {sx , sy};
    st[sx][sy] = 1;
    Q.push(fi);

    while(Q.size()){

        now = Q.front();
        Q.pop();
        area++;

        for(int i = 0; i < 4; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(st[nx][ny] || nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[now.x][now.y] >> i & 1) continue;

            ne = {nx , ny};
            st[nx][ny] = 1;
            Q.push(ne);

        }
    }

    return area;
}

int main(){

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

    cnt = 0 , maxn = 0;        
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++) 
            if(!st[i][j]){

                cnt ++;
                maxn = max(maxn , bfs(i , j));
            }

    cout << cnt << endl;
    cout << maxn << endl;

    return 0;

}

1106.山峰和山谷

题意：对于给定的地图，求出山峰和山谷的数量

8联通 ，用flood fill算法

因为是高度地图 ，

如果我们走到某一连通块的边界时 ，判断一下 ，边界外的点的高度比当前点高 ，当前点所在的连通块就是山谷 ， 反之就是山峰。

如果没到边界 ，那么正常入队列扩展。

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int , int > PII;

const int N = 1e3 + 10;

int n;
bool high , low;
int h[N][N];
bool st[N][N];
PII fi , ne , now;
int dx[] = {0 , -1 , 0 , 1 , -1 , 1 , -1 , 1} , dy[] = {-1 , 0 , 1 , 0 , -1 , -1 , 1 , 1};

void bfs(int sx , int sy){

    queue<PII> Q;
    fi = {sx , sy};
    st[sx][sy] = 1;
    Q.push(fi);

    while(Q.size()){

        now = Q.front();
        Q.pop();

        for(int i = 0; i < 8; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            if(h[nx][ny] != h[now.x][now.y]){

                if(h[nx][ny] > h[now.x][now.y]) high = 1;
                else low = 1;

            }
            else if(!st[nx][ny]){
                ne = {nx , ny};
                st[nx][ny] =1;
                Q.push(ne);
            }
        }
    }
}

int main(){

    cin >> n;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            cin >> h[i][j];

    int feng = 0 , gu = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(!st[i][j]){

                high = 0 , low = 0; // high标志表示是否有区域比当前区域高
                bfs(i , j);

                if(!high) feng++;
                if(!low) gu ++;

            }

    cout << feng << " " << gu << endl;

    return 0;
}

BFS最短路模型

因为BFS在图中逐层向外扩展的特性 ， 只要一张图中边权都为一个相同的固定值 ，那么从起点开始 ，第一次扩展到的点一定是起点到它的最短路径 。

1076迷宫问题

题意：输出矩阵图从左上角到右下角的最短路线

按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)(0,0)，右下角坐标为 (n−1,n−1)(n−1,n−1)。

矩阵图求最短路 ， 用bfs最短路模型

这题需要输出路径坐标 ，那么对st标记数组做修改，改为一个pair数组

记录的是这个点坐标是由哪个点坐标走过来的

这样我们从终点开始bfs ，走到起点后退出

数组内从起点开始打印 ，顺序正好就是从起点到终点的路径。

pre[8 , 9] = {7 , 7}; pre[7 , 7] = {7 , 5}
/*代表（8 ， 9）这个点是从（7 ， 7）这个点走过来的 , (7 , 7)这个点又是从（7 ， 5）走来的
所以路径为（7 ， 5） --> （7 ， 7） --> (8 , 9)
*/

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

#define x first
#define y second

typedef pair<int , int > PII;

int n;
PII pre[N][N] , now , fi , ne;
int g[N][N] , dx[] = {0 , -1 , 0 , 1} , dy[] = {-1 , 0 , 1 , 0};

void bfs(int sx , int sy){

    memset(pre , -1 , sizeof pre); // pre同时可以兼作标记数组
    queue<PII> Q;
    fi = {sx , sy};
    Q.push(fi);
    pre[sx][sy] = {0 , 0};

    while(Q.size()){

        now = Q.front();
        Q.pop();

        for(int i = 0; i < 4; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if(g[nx][ny]) continue; // 有墙不能走
            if(pre[nx][ny].x != -1) continue; // 有别的点走过了，不能走

            ne = {nx , ny};
            Q.push(ne);
            pre[nx][ny] = {now.x , now.y}; // nx,ny这个点是由now.x , now.y 走过来的

        }
    }

}

int main(){

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

    bfs(n - 1 , n - 1);

    PII end = {0 , 0}; // 初始化从起点开始走
    while(1){

        printf("%d %d\n" , end.x , end.y);

        if(end.x == n - 1 && end.y == n - 1) break; // 到了终点结束循环

        end = pre[end.x][end.y];

    }

    return 0;
}

188.武士风度的牛

题意：从地图上的‘K’ 走到‘H’最短需要多少步

分析：宽搜求最短路

​ 注意这里的牛走的是日字，

​ 第1行： 两个数，表示农场的列数C和行数R输入的时候注意。

#include<bits/stdc++.h>

using namespace std;

const int N = 155;

#define x first
#define y second

typedef pair<int , int > PII;

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

int bfs(){

    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; // 日字型

    int sx , sy;
    for(int i = 0; i < n; i ++)
        for(int j = 0 ; j < m ; j ++)
            if(g[i][j] == 'K') sx = i , sy = j;

    queue<PII> Q;
    PII fi = {sx , sy};
    memset(dist , -1 , sizeof dist);
    Q.push(fi);
    dist[sx][sy] = 0;

    while(Q.size()){

        PII now = Q.front();
        Q.pop();

        for(int i = 0; i < 8; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(g[nx][ny] == '*' || nx < 0 || nx >= n || ny < 0 || ny >= m || dist[nx][ny] != -1) continue;

            if(g[nx][ny] == 'H') return dist[now.x][now.y] + 1;

            PII ne = {nx , ny};
            dist[nx][ny] = dist[now.x][now.y] + 1;
            Q.push(ne);

        }
    }

    return -1; 
}

int main( ){

    cin >> m >> n;
    for(int i = 0; i < n; i ++) scanf("%s" , g[i]);

    cout << bfs() << endl;

    return 0;
}

1100.抓住那头牛

题意：数轴上起始点N走到K的最短路长度

分析：

​ bfs求最短路

​ 因为每次执行一次操作 ，所以从N出发能到的点在队列中其实符合按层扩展的特性 ，

​ 队头的点是相对于 队列中 和 还没扩展到的点 步数最少的。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n , k;
int dist[N];

int bfs(){

    memset(dist , -1 , sizeof dist);
    queue<int > Q;
    dist[n] = 0;
    Q.push(n);

    while(Q.size()){

        int now = Q.front();
        Q.pop();

        if(now == k) return dist[now];

        if(dist[now + 1] == -1 && now + 1 < N) dist[now + 1] = dist[now] + 1 , Q.push(now + 1);
        if(dist[now - 1] == -1 && now - 1 >= 0) dist[now - 1] = dist[now] + 1 , Q.push(now - 1);
        if(dist[now * 2] == -1 && now * 2 < N) dist[now * 2] = dist[now] + 1 , Q.push(now * 2);


    }

    return -1;

}

int main(){

    cin >> n >> k;

    if(n > k) cout <<n - k << endl; 
    else cout << bfs() << endl;

    return 0;
}

BFS求多源最短路

因为bfs队列的单调性和两段性 ，保证了队头更新过距离的点一定不会再被没有入队的点更新最短距离 。

所以bfs求多源最短路可以在队列的第一层直接将所有起点入队 ，后面照常扩展

性质保证了队头更新的点距离一定是最短的

173.矩阵距离

题意：求矩阵中所有点到离它最近的1的距离 ，以距离矩阵的形式输出

分析 ：起点为所有的1 ， 我们可以把所有的1初始直接入队 ，正常用bfs求每个起点到每个点的最短距离即可

#include<bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

#define x first
#define y second

typedef pair<int , int > PII;

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

void bfs(){

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

    memset(dist , -1 , sizeof dist);
    queue<PII> Q;

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(g[i][j] == '1'){

                dist[i][j] = 0;
                Q.push({i , j});
            }

    while(Q.size()){

        PII now = Q.front();
        Q.pop();

        for(int i = 0; i < 4; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m || dist[nx][ny] != -1) continue;

            Q.push({nx , ny});
            dist[nx][ny] = dist[now.x][now.y] + 1;

        }
    }
}    

int main(){

    cin >> 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]);
        }
        cout << endl;
    }

    return 0;
} 

一些习题

FloodFill

1233.全球变暖

题意：给定一张矩阵图 ，其中的 ‘.’ 会向四联通方向蔓延，求蔓延一次之后图中没有被完全覆盖的连通块的数量。

分析：

​ 矩阵图求连通块 ，首选floodfill ，题目要求周围的 ‘.’ 会向四联通蔓延一次 ，正着求蔓延完了的图肯定不好求 ，

​ 反着想 ，floodfill求’#‘ 连通块时对于扩展到的每一块陆地 ，我们向它的4联通方向检查一次 ，如果有 ’.‘ 它就会被淹没 记一次数 ，最后和一整个连通块中的点的总数比较 ，如果计数和总数相同 ，那么整个连通块都会被淹没，否则就是没被完全淹没。

#include<bits/stdc++.h>

using namespace std;

typedef pair<int , int > PII;

#define x first
#define y second

const int N = 1010;

int n;
char g[N][N];
bool st[N][N];

int bfs(int sx , int sy){

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

    int sum = 0 , sea = 0;
    st[sx][sy] = 1;
    queue<PII> Q;
    Q.push({sx , sy});

    while(Q.size()){

        PII now = Q.front();
        Q.pop();
        sum++;

        for(int i = 0; i < 4; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(g[nx][ny] == '.'）{
                sea++;
                break;
            }
        }

        for(int i = 0; i < 4; i ++){

            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= n || st[nx][ny] || g[nx][ny] == '.') continue;

            st[nx][ny] = 1;
            Q.push({nx , ny});

        }
    }

    //cout << sum << " " << sea << endl;

    if(sum == sea) return 1;
    else return 0;
}

int main(){

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

    int cnt = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(!st[i][j] && g[i][j] == '#') if(bfs(i , j)) cnt++;

    cout << cnt << endl;

    return 0;

}

BFS求最小步数

以8数码为典型例子 ，求一种状态到另一种状态的最小步数

这里区别于之前的bfs的是，队列扩展的内容是一种状态 （例如一张九宫格图就是一种状态） ，直到队头到达我们需要的状态结束。

队列扩展过程更加类似于一张有向图 ，每一个节点是一种状态。它向下一个状态建一条有向边 ，我们所求的就是起点到目标节点的最短距离。

1107.魔板

题意：给定基础序列 ，给了三种操作 ，求到目标序列的最小步数

分析：与八数码类似 ，哈希存状态进行bfs。

最小字典序的问题只需要我们在操作时按照ABC的顺序来入队即可 ，因为队列两段性

//假设当前队列中由ABC扩展进来：

队列Q：X（A） ， X(B)， X(C) , X+1(A) , X+1(B) , X+1(C)

因为A操作的X+1（A）由X（A） 扩展得到
由于初始队列内顺序：X（A） ， X(B)， X(C) 
所以由所有X扩展而来的 X + 1 也是保持ABC的字典序

#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];
}

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);
    int 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();
}

string move2(string state)
{
    set(state);
    int 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;
    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]))
            {
                dist[m[i]] = dist[t] + 1;
                pre[m[i]] = {'A' + i, t};
                q.push(m[i]);
                if (m[i] == end) return dist[end];
            }
    }

    return -1;
}

int main()
{
    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;

    string res;
    while (end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }

    reverse(res.begin(), res.end());

    if (step > 0) cout << res << endl;

    return 0;
}

双端队列广搜

双端队列是一种特殊的队列 ，队首和队尾都可以入队和出队

175.电路维修

题意：在只能斜着走（电线看可以旋转）的电路图中输出从左上走到右下的最小旋转电路次数

分析：

这题区别一般bfs ，图中电线可以旋转 ，普通的广搜是在一张严格的边权0或1的无向图中 ，

对于这题我们有“/” ， “\” ,两种状态 ，又因为起点在左上 ，所以我们把’\‘ 看成边权为0 ， “/”需要旋转就看成边权为1 ，这样就得到了一张边权为0 ， 1的无向图 ，

用双端队列的原因是我们的边权为0 ， 1其实都可以走 ，

如果说当前新状态的边权为0,那么我们就放到队头先走,因为两端性和单调性,如果说当前新状态边权为1,那么我们就只能压入到队尾

#include<bits/stdc++.h>

using namespace std;

typedef pair<int , int > PII;

#define x first
#define y second

const int N = 510;

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

int bfs(){

    deque<PII> Q;
    memset(st , 0 , sizeof st);
    memset(dist , 0x3f , sizeof dist);
    Q.push_back({0 , 0});
    dist[0][0] = 0;

    char cs[] = "\\/\\/";
    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 now = Q.front();
        Q.pop_front();

        int xx = now.x , yy = now.y;
        if(st[xx][yy]) continue;
        st[xx][yy] = 1;

        for(int i = 0;  i < 4; i ++){

            int nx = xx + dx[i];
            int ny = yy + dy[i];

            if(nx < 0 || nx > n || ny < 0 || ny > m) continue;

            int ca = xx + ix[i] , cb = yy + iy[i];
            int d = dist[xx][yy] + (g[ca][cb] != cs[i]);

            if(d < dist[nx][ny]){

                dist[nx][ny] = d;

                if(g[ca][cb] != cs[i]) Q.push_back({nx , ny});
                else Q.push_front({nx , ny});

            }
        }
    }
    return dist[n][m];

}

int main(){

    int T;
    cin >> T;
    while(T--){

        cin >> n >> m;
        for(int i = 0; i < n; i ++) scanf("%s" , g[i]);

        if(n + m & 1) cout << "NO SOLUTION" << endl;
        else cout << bfs() << endl;
    }

    return 0;
}

双向广搜

广搜的一种优化方式 ，多用于最小步数模型这种需要搜状态的模型 ，如果单一从起点搜索 ，队列内存的状态过多 ，MLE ，TLE都可能会发生 。

双向指的是从起点和终点同时开始搜 ，类似两头会师，会极大地降低同时存在队列内的状态数。

190.字串变换

题意：已知原字符串和目标字符串 ，给定变换操作，求最小步数

分析：bfs最小步数模型+双向广搜优化

#include<bits/stdc++.h>

using namespace std;

const int N = 6;

int n;
string a[N], b[N];

int extend(queue<string>& q, unordered_map<string, int>& da, unordered_map<string, int>& db, string a[], string b[]){
    for (int k = 0, sk = q.size(); k < sk; k ++ ){
        string t = q.front();
        q.pop();

        for (int i = 0; i < t.size(); i ++ )
            for (int j = 0; j < n; j ++ )
                if (t.substr(i, a[j].size()) == a[j])
                {
                    string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
                    if (da.count(state)) continue;
                    if (db.count(state)) return da[t] + 1 + db[state];
                    da[state] = da[t] + 1;
                    q.push(state);
                }
    }

    return 11;
}

int bfs(string A, string B){
    queue<string> qa, qb;
    unordered_map<string, int> da, db;
    qa.push(A), da[A] = 0;
    qb.push(B), db[B] = 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;
    }

    return 11;
}

int main(){
    string A, B;
    cin >> A >> B;
    while (cin >> a[n] >> b[n]) n ++ ;

    int step = bfs(A, B);
    if (step > 10) puts("NO ANSWER!");
    else printf("%d\n", step);

    return 0;
}

A*

A* ，一种搜索的优化方式 ，类似一种边搜索 ，边猜测当前与实际终点的距离 ，从而选择更近的搜素路径。

179.八数码

#include<bits/stdc++.h>

using namespace std;

int f(string state){
    int res = 0;
    for (int i = 0; i < state.size(); i ++ )
        if (state[i] != 'x'){

            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}

string bfs(string start){
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    char op[4] = {'u', 'r', 'd', 'l'};

    string end = "12345678x";
    unordered_map<string, int> dist;
    unordered_map<string, pair<string, char>> prev;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;

    heap.push({f(start), start});
    dist[start] = 0;

    while (heap.size()){

        auto t = heap.top();
        heap.pop();

        string state = t.second;

        if (state == end) break;

        int step = dist[state];
        int x, y;
        for (int i = 0; i < state.size(); i ++ )
            if (state[i] == 'x'){

                x = i / 3, y = i % 3;
                break;
            }
        string source = state;
        for (int i = 0; i < 4; i ++ ){
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3){

                swap(state[x * 3 + y], state[a * 3 + b]);
                if (!dist.count(state) || dist[state] > step + 1){

                    dist[state] = step + 1;
                    prev[state] = {source, op[i]};
                    heap.push({dist[state] + f(state), state});
                }
                swap(state[x * 3 + y], state[a * 3 + b]);
            }
        }
    }

    string res;
    while (end != start){

        res += prev[end].second;
        end = prev[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main(){
    string g, c, seq;
    while (cin >> c){

        g += c;
        if (c != "x") seq += c;
    }

    int t = 0;
    for (int i = 0; i < seq.size(); i ++ )
        for (int j = i + 1; j < seq.size(); j ++ )
            if (seq[i] > seq[j])
                t ++ ;

    if (t % 2) puts("unsolvable");
    else cout << bfs(g) << endl;

    return 0;
}

提高课图论

单源最短路的建图方式

1129.热浪

求起点到终点的最短路长度

spfa

#include<bits/stdc++.h>

using namespace std;

const int N = 2510 , M = 2 * 6200 + 10;

int  n , m , S , T , idx;
int dist[N];
bool st[N];
int h[N] , e[M] , ne[M] , w[M];

void add(int a , int b , int c){

    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}

void spfa(){

    memset(dist , 0x3f , sizeof dist);
    queue<int> Q;
    Q.push({S});
    dist[S] = 0;

    while(Q.size()){

        int t = Q.top();
        Q.pop();
        st[t] = 0;

        for(int i = h[t]; ~i ; i = ne[i]){

            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];

                if(!st[j]) Q.push(j) , st[j] = 1;

            }
        }
    }

}

int main(){

    memset(h , -1 , sizeof h);

    cin >> n >> m >> S >> T;

    for(int i = 0; i < m; i ++){

        int a , b  ,c;
        cin >> a >> b >> c;

        add(a , b , c) , add(b , a , c);

    }

    spfa();

    cout << dist[T] << endl;

    return 0;

}

dij

#include<bits/stdc++.h>

using namespace std;

typedef pair<int , int > PII;

const int N = 2510 , M = 2 * 6200 + 10;

int  n , m , S , T , idx;
int dist[N];
bool st[N];
int h[N] , e[M] , ne[M] , w[M];

void add(int a , int b , int c){

    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}

void dij(){

    memset(dist , 0x3f , sizeof dist);
    priority_queue<PII , vector<PII > , greater<PII>> Q;
    Q.push({0 , S});
    dist[S] = 0;

    while(Q.size()){

        PII now = Q.top();
        Q.pop();
        int t = now.second , dis = now.first;

        if(st[t]) continue;
        st[t] = 1;

        for(int i = h[t]; ~i ; i = ne[i]){

            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                Q.push({dist[j] , j});

            }
        }
    }

}

int main(){

    memset(h , -1 , sizeof h);

    cin >> n >> m >> S >> T;

    for(int i = 0; i < m; i ++){

        int a , b  ,c;
        cin >> a >> b >> c;

        add(a , b , c) , add(b , a , c);

    }

    dij();

    cout << dist[T] << endl;

    return 0;

}

1128.信使

求以1为起点到所有点的最短路的最大值

floyd

#include<bits/stdc++.h>

using namespace std;

const int N = 110 , INF = 0x3f3f3f3f;

int n , m;
int d[N][N];


int main(){

    memset(d , 0x3f , sizeof d);

    cin >> n >> m;
    for(int i = 0; i < m; i ++){

        int a , b , c;
        cin >> a >> b >> c;

        d[a][b] = d[b][a] = min(d[a][b] , c);
    }

    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                d[i][j] = min( d[i][j] , d[i][k] + d[k][j]);

    int maxn = 0;
    for(int i = 1; i <= n; i ++){

        if(d[1][i] == INF){
            maxn = -1;
            break;
        }
        else maxn = max(maxn , d[1][i]);
    }

    cout << maxn << endl;

    return 0;
}

1127.香甜的黄油

求以哪个点为起点 ，图中给定的点到起点的最短路和最小

n遍spfa

#include<bits/stdc++.h>

using namespace std;

const int N = 810 , M = 3000 , INF = 0x3f3f3f3f;

int n , p , m;
int d[N] , id[N];
bool st[N];
int h[N] , w[M] , e[M] , ne[M] , idx;

void add(int a , int b , int c){

    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}

int spfa(int sx){

    memset(d , 0x3f , sizeof d);
    queue<int> Q;
    d[sx] = 0;
    st[sx] = 1;
    Q.push(sx);

    while(Q.size()){

        int t = Q.front();
        Q.pop();
        st[t] = 0;

        for(int i = h[t]; ~i ; i = ne[i]){
            int j = e[i];

            if(d[j] > d[t] +  w[i]){
                d[j] = d[t] + w[i];

                if(!st[j]) Q.push(j) , st[j] = 1;
            }
        }

    }

    int res = 0;
    for(int i = 0; i < n; i ++){

        if(d[id[i]] == INF) return INF;
        res += d[id[i]];
    }

    return res;
}

int main(){

    memset(h , -1 , sizeof h);

    cin >> n >> p >> m;

    for(int i = 0; i < n; i++) cin >> id[i];

    for(int i = 0; i < m; i ++){

        int a , b , c;
        cin >> a >> b >> c;

        add(a , b  ,c) , add(b , a , c);

    }

    int res = INF;
    for(int i = 1; i <= p; i ++) res = min(res , spfa(i));

    cout << res << endl;

    return 0;
}