BFS经典问题

• 八数码问题题解
• 图中点的层次问题题解

  八数码问题：

https://www.acwing.com/problem/content/847/

思路：

题目使用了一个数组来存矩阵 例：1 2 3 4 5 6 7 8 x 表示

1 2 3
4 5 6
7 8 x

可以将每一种矩阵状态看做一个点，用c11的unordered_map将距离与每个状态对应，使用BFS遍历求最短路 需要思考的问题：如何实现一个状态到其他状态的转移

代码实现：

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

using namespace std;

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

string End = "12345678x";

int bfs(string start)
{
    queue<string> q;
    q.push(start);
    unordered_map<string, int> d;
    d[start] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        if (t == End)
            return d[t];
        int dis = d[t];
        int k = t.find('x');
        int y = k / 3, x = k % 3;       //将当前状态的 x 的坐标表示出来
        for (int i = 0; i < 4; i++)
        {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3)
            {
                swap(t[k], t[x1 + y1 * 3]);
                if (!d.count(t))
                {
                    d[t] = dis + 1;
                    q.push(t);
                }
                swap(t[k], t[x1 + y1 * 3]);
            }
        }
    }
    return -1;
}

int main()
{
    string start;
    for (int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        start += c;
    }
    cout << bfs(start) << endl;
    return 0;
}

图中点的层次 ：

题面

给定一个n个点m条边的有向图，图中可能存在重边和自环。所有边的长度都是1，点的编号为1~n。 请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式

第一行包含两个整数n和m。 接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

数据范围

1 ≤ n, m ≤ 1e5

思路：

裸题，可以将1号点放入队头开始BFS的过程，每次扩展队头时记录 dis 数组记录1号点到当前点的距离(1号点距离初始化为0)，注意该题所有边的长度都是1，所以可以使用BFS求最短路

代码实现：

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

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx, dis[N];

int n, m;

void add(int a, int b)
{
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

int bfs()
{
    queue<int> q;
    dis[1] = 0;     //1号点距离初始化为0
    q.push(1);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dis[j] == -1)        //判断j点是否扩展过（自环、重边）
            {
                dis[j] = dis[t] + 1;
                q.push(j);
            }
        }
    }
    return dis[n];
}

int main()
{
    memset(dis, -1, sizeof dis);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    cout << bfs() << endl;
    return 0;
}