《算法竞赛进阶指南》0x25 广度优先搜索

一只野生彩色铅笔

发布于 2022-10-31 11:06:36

6290

发布于 2022-10-31 11:06:36

文章被收录于专栏：彩铅的随笔博客彩铅的随笔博客

广度优先搜索

如果我们把状态空间比作一张图，那么广度优先搜索就相当于对这张图的广度优先遍历

类似的，我们依然借助一个队列来实现广度优先搜索，起初队列中仅包含起始状态

在广度优先搜索的过程中，我们不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一个状态（如果未访问过或者能够被更新成更优的解）插入队尾

重复执行上述过程直到队列为空

习题

立体推箱子

题目描述

立体推箱子是一个风靡世界的小游戏。

游戏地图是一个

行

列的矩阵，每个位置可能是硬地（用 . 表示）、易碎地面（用 E 表示）、禁地（用 # 表示）、起点（用 X 表示）或终点（用 O 表示）。

你的任务是操作一个

1×1×2

的长方体。

这个长方体在地面上有两种放置形式，“立”在地面上（

1×1

的面接触地面）或者“躺”在地面上（

1×2

的面接触地面）。

在每一步操作中，可以按上下左右四个键之一。

按下按键之后，长方体向对应的方向沿着棱滚动

度。

任意时刻，长方体不能有任何部位接触禁地，并且不能立在易碎地面上。

字符 X 标识长方体的起始位置，地图上可能有一个 X 或者两个相邻的 X。

地图上唯一的一个字符 O 标识目标位置。

求把长方体移动到目标位置（即立在 O 上）所需要的最少步数。

在移动过程中，X 和 O 标识的位置都可以看作是硬地被利用。

输入格式

输入包含多组测试用例。

对于每个测试用例，第一行包括两个整数

和

。

接下来

行用来描述地图，每行包括

个字符，每个字符表示一块地面的具体状态。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需考虑。

输出格式

每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。

每个结果占一行。

数据范围

3≤N,M≤500

输入样例：

7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0

输出样例：

解析

将箱子的三个摆放形式看做三个点，进行拆点 bfs 求最短路即可

思路不难，代码一百行，调的头疼

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

using namespace std;

const int N = 510;

struct Node
{
    int x, y, st;   //0立，1横，2竖
    bool operator == (const Node& t) const
    {
        return x == t.x && y == t.y && st == t.st;
    }
};

int n, m;
char g[N][N];
int d[N][N][3];

const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
Node st, ed;
bool valid(int x, int y)    //边界判断
{
    return x && x <= n && y && y <= m;
}
bool valid(Node t)    //障碍判断
{
    if (!valid(t.x, t.y)) return false;
    if (g[t.x][t.y] == '#') return false;
    if (t.st == 0 && g[t.x][t.y] == 'E') return false;
    if (t.st == 1 && g[t.x][t.y - 1] == '#') return false;
    if (t.st == 2 && g[t.x - 1][t.y] == '#') return false;
    return true;
}
void init()
{
    for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ )
    {
        if (g[i][j] == 'O') ed = {i, j}, g[i][j] = '.';
        else if (g[i][j] == 'X')
        {
            st = {i, j, 0};
            g[i][j] = '.';
            for (int k = 0; k < 4; k ++ )
            {
                int x = i + dx[k], y = j + dy[k];
                if (valid(x, y) && g[x][y] == 'X')
                {
                    st = {x, y};
                    if (k & 1) st.st = 2;
                    else st.st = 1;
                    g[x][y] = '.';
                }
            }
        }
    }
}

const int nx[3][4] = {{0, 2, 0, -1}, {0, 1, 0, -1}, {0, 1, 0, -2}};
const int ny[3][4] = {{2, 0, -1, 0}, {1, 0, -2, 0}, {1, 0, -1, 0}};
const int ns[3][4] = {{1, 2, 1, 2}, {0, 1, 0, 1}, {2, 0, 2, 0}};

int bfs()
{
    memset(d, -1, sizeof(d));
    d[st.x][st.y][st.st] = 0;
    
    queue<Node> q;
    q.push(st);
    
    while (q.size())
    {
        Node top = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ )
        {
            Node next = 
            {
                top.x + nx[top.st][i],
                top.y + ny[top.st][i],
                ns[top.st][i]
            };
            if (!valid(next)) continue;
            if (~d[next.x][next.y][next.st]) continue;
            d[next.x][next.y][next.st] = d[top.x][top.y][top.st] + 1;
            if (next == ed) return d[next.x][next.y][next.st];
            q.push(next);
        }
    }
    return -1;
}
int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);
        init();
        int res = bfs();
        if (~res) printf("%d\n", res);
        else puts("Impossible");
    }
    return 0;
}

矩阵距离

题目描述

给定一个

行

列的

矩阵

，

A[i][j]

与

A[k][l]

之间的曼哈顿距离定义为：

[ dist(A[i][j],A[k][l])=|i−k|+|j−l| ]

输出一个

行

列的整数矩阵

，其中：

[ B[i][j]=\min_{1≤x≤N,1≤y≤M,A[x][y]=1}dist(A[i][j],A[x][y]) ]

输入格式

第一行两个整数

N,M

。

接下来一个

行

列的

矩阵，数字之间没有空格。

输出格式

一个

行

列的矩阵

，相邻两个整数之间用一个空格隔开。

数据范围

1≤N,M≤1000

输入样例：

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

解析

假设整个 01 矩阵只有一个 1，其余全是 0

则求所有点到 1 的最短距离，等价于求这个 1 到其他所有点的最短距离

于是就可以以 1 为起点做一遍 BFS 即可

对于任意 01 矩阵，求所有点到 1 的最短距离，等价于所有的 1 到其他所有点的最短距离

于是原问题就变成了多源点最短路问题，做一个超级源点或者一开始起点全部加入队列都可

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

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

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool valid(int x, int y)
{
    return x && x <= n && y && y <= m;
}
int bfs()
{
    memset(d, -1, sizeof d);
    queue<PII> q;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (g[i][j] == '1')
                q.push({i, j}), d[i][j] = 0;
    while (q.size())
    {
        PII top = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ )
        {
            int x = top.x + dx[i], y = top.y + dy[i];
            if (!valid(x, y)) continue;
            if (~d[x][y]) continue;
            d[x][y] = d[top.x][top.y] + 1;
            q.push({x, y});
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);
    bfs();
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            printf("%d ", d[i][j]);
        }
        puts("");
    }
    return 0;
}

推箱子

题目描述

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把

个箱子到目的地。

给定一张

行

列的地图，用字符 . 表示空地，字符 # 表示墙，字符 S 表示人的起始位置，字符 B 表示箱子的起始位置，字符 T 表示箱子的目标位置。

求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。

方案中使用大写的 EWSN（东西南北）表示箱子的移动，使用小写的 ewsn（东西南北）表示人的移动。

输入格式

输入包含多个测试用例。

对于每个测试用例，第一行包括两个整数

N，M

。

接下来

行，每行包括

个字符，用以描绘整个

行

列的地图。

当样例为

N=0，M=0

时，表示输入终止，且该样例无需处理。

输出格式

对于每个测试用例，第一行输出 Maze # + 测试用例的序号。

第二行输入一个字符串，表示推箱子的总体移动过程，若无解，则输出 Impossible.。

每个测试用例输出结束后输出一个空行。

若有多条路线满足题目要求，则按照 N、S、W、E 的顺序优先选择箱子的移动方向（即先上下推，再左右推）。

在此前提下，再按照 n、s、w、e 的顺序优先选择人的移动方向（即先上下动，再左右动）。

数据范围

1≤N,M≤20

输入样例：

1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0

输出样例：

Maze #1
EEEEE

Maze #2
Impossible.

Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN

Maze #4
swwwnnnnnneeesssSSS

解析

首先这题拆点拆不了，如果把人和箱子的坐标都记录下来，则拆点后的距离也是多关键字：

(d_{箱},d_{人})

但是这就出现了一个问题，BFS 每次扩展时，可能是箱子距离 + 1，可能是人的距离 + 1，还有可能是两者都 + 1

这就破坏了 BFS 辅助队列的单调性，即如果当前队列中被更新的状态符合单调性，但是队尾相对队头是两者都 + 1，如果此时队头元素又更新出来一个只有二者其中之一 + 1 的状态，此时是无法插入队尾了，于是就破坏了辅助队列的单调性

这种情况比较常见的就是，边权不是全 1 时的图最短路问题，解决方法是转而用堆来存储状态，也就是 BFS 变 Dijkstra

如果本题我们也考虑用堆来作为辅助，则每轮操作会多一个

\log

，计算一下时间复杂度：

O(4^2n^4 \log n^4)

时间复杂度直接拉满，本题又是多样例，故肯定会超时，考虑其他解法

蓝书上给出了非常漂亮的做法：双重BFS

每推一次箱子所要经历的步骤：人先移动到箱子的一侧，箱子再向着人的反向移动，人最后取代箱子的位置

则 BFS 的状态存储就可以用三元组完成：

\{x, y, dir\}

，其中

(x,y)

是箱子坐标，

dir

是人位于箱子四相邻的方向

每次从队头取出一个元素后，进行状态更新的步骤如下：

箱子在

(x,y)

不动，人用尽量少的步数从起点

(x-dx[dir],y-dy[dir])

移动到终点

(x-dx[k], y-dy[k])

，且中途不能经过

(x,y)

人沿着

方向推一次箱子，箱子移动到

(x+dx[k],y+dy[k])

，人移动到

(x,y)

将新状态入队，并且把箱子移动步数

f_{box}

和人移动步数

f_{man}

更新

该双重BFS在每一轮中做了两次BFS，为了代码格式养眼，调试方便，考虑将两次 BFS 处理成两个模块调用

输出方案就很简单，对于已有的状态数组，以及目标状态，进行一波倒推即可

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

#define x first
#define y second

using namespace std;

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

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

int n, m;
char g[N][N];
bool stman[N][N];
PII dist[N][N][4];

vector<int> path[N][N][4];
Node pre[N][N][4];

bool valid(int x, int y)
{
    return x && x <= n && y && y <= m && g[x][y] != '#';
}
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

int bfs_man(PII start, PII end, PII box, vector<int> &seq)
{
    static int pre[N][N];
    memset(pre, -1, sizeof(pre));
    memset(stman, 0, sizeof(stman));
    stman[start.x][start.y] = true;
    stman[box.x][box.y] = true;
    queue<PII> q;
    q.push({start.x, start.y});
    while (q.size())
    {
        PII top = q.front(); q.pop();
        if (end == top)
        {
            for (int x = top.x, y = top.y; ~pre[x][y]; )
            {
                int d = pre[x][y];
                seq.push_back(d);
                x = x + dx[d ^ 1], y = y + dy[d ^ 1];
            }
            return seq.size();
        }
        for (int i = 0; i < 4; i ++ )
        {
            int x = top.x + dx[i], y = top.y + dy[i];
            if (valid(x, y) && !stman[x][y])
            {
                pre[x][y] = i;
                stman[x][y] = true;
                q.push({x, y});
            }
        }
    }
    return -1; 
}
bool bfs(Node& end)
{
    memset(dist, -1, sizeof(dist));
    memset(pre, -1, sizeof(pre));
    //find the people position and intialize the point
    PII stm, stb;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (g[i][j] == 'S') stm = {i, j}, g[i][j] = '.';
            else if (g[i][j] == 'B') stb = {i, j}, g[i][j] = '.';
    
    //insert the start point into the bfs auxiliary queue
    queue<Node> q;
    for (int i = 0; i < 4; i ++ )
    {
        int x = stb.x - dx[i], y = stb.y - dy[i];
        if (!valid(x, y)) continue;
        
        vector<int> seq;
        int cnt = bfs_man(stm, {x, y}, stb, seq);
        if (cnt != -1)
        {
            //for (auto it: seq) cout << it << " "; cout << endl;
            dist[stb.x][stb.y][i] = {0, cnt};
            path[stb.x][stb.y][i] = seq;
            q.push({stb.x, stb.y, i});
        }
    }
    
    PII res = {1e9, 1e9};
    bool flag = false;
    while (q.size())
    {
        Node top = q.front(); q.pop();
        //printf("man:%d %d box:%d %d dir:%d\n", top.x - dx[top.dir], top.y - dy[top.dir], top.x, top.y, top.dir);
        // check the end
        if (g[top.x][top.y] == 'T')
        {
            flag = true;
            if (res > dist[top.x][top.y][top.dir])
            {
                res = dist[top.x][top.y][top.dir];
                end = top;
            }
            continue;
        }

        PII man_pos = {top.x - dx[top.dir], top.y - dy[top.dir]};   //position the man locates
        //find other trans path
        for (int k = 0; k < 4; k ++ )
        {
            int bx = top.x + dx[k], by = top.y + dy[k]; //the goal of the box
            int px = top.x - dx[k], py = top.y - dy[k]; //the position man need to reach
            if (!valid(px, py) || !valid(bx, by)) continue;
            //try to push the box
            vector<int> seq;
            int cnt = bfs_man(man_pos, {px, py}, {top.x, top.y}, seq);
            if (cnt != -1)  //cal the distance
            {
                PII temp = {dist[top.x][top.y][top.dir].x + 1, dist[top.x][top.y][top.dir].y + cnt};
                if (dist[bx][by][k].x == -1)
                {
                    pre[bx][by][k] = top;
                    path[bx][by][k] = seq;
                    dist[bx][by][k] = temp;
                    q.push({bx, by, k});
                }
                else if (dist[bx][by][k] > temp)
                {
                    pre[bx][by][k] = top;
                    path[bx][by][k] = seq;
                    dist[bx][by][k] = temp;
                }
            }
        }
    }
    //cout << end.x << " " << end.y << endl;
    return flag;
}
int main()
{
    int T = 1;
    while (scanf("%d%d", &n, &m), n || m)
    {
        printf("Maze #%d\n", T ++ );
        for (int i = 1; i <= n; i ++ ) scanf("%s", g[i] + 1);
        Node end;
        if (!bfs(end)) puts("Impossible.");
        else
        {
            char ops[] = {"nswe"};
            string res;
            while (pre[end.x][end.y][end.dir].dir != -1)
            {
                //cout << end.x << " " << end.y << " " << end.dir << endl;
                res += ops[end.dir] - 32;
                for (auto dir: path[end.x][end.y][end.dir]) res += ops[dir];
                end = pre[end.x][end.y][end.dir];
            }
            if (path[end.x][end.y][end.dir].size())
                for (auto dir: path[end.x][end.y][end.dir]) res += ops[dir];
            reverse(res.begin(), res.end());
            cout << res << endl;
        }
        puts("");
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-02-14，如有侵权请联系 cloudcommunity@tencent.com 删除

uml

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

uml

登录后参与评论

0 条评论

热度