上海计算机学会 2023年12月月赛 丙组T4 迷宫（宽度优先搜索）

第四题：T4迷宫

标签：宽度优先搜索
题意：给定$n$x$m$由$\#$（墙）、$.$（空地）组成的地图，求从左上角到右下角的最少步数，每次只允许上下左右移动一格，不允许走出地图和走到$\#$（墙）上。
题解：BFS 模板题，判断下一个能否走的点，经典三要素：

1. 下个点是否是障碍物（宽泛来说是题目中的限制条件）
2. 下个点是否走过（避免死循环）
3. 下个点是否在地图内

代码：

#include <bits/stdc++.h>
using namespace std;

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

char a[1005][1005];
bool vis[1005][1005];
struct node {
    int x, y, step;
};

void bfs() {
    queue <node> q;
    vis[1][1] = 1;
    q.push({1, 1, 0});
    while (!q.empty()) {
        node u = q.front();
        q.pop();
        if (u.x == n && u.y == m) {
            cout << u.step << endl;
            return ;
        }
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (vis[nx][ny] || a[nx][ny] == '#') continue;
            vis[nx][ny] = 1;
            q.push({nx, ny, u.step + 1});
        }
    }
    cout << "No solution" << endl;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    cin >> a[i][j];
    bfs();
    return 0;
}

原文地址：https://blog.csdn.net/oitutor/article/details/136446635

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！