地牢逃脱 (BFS)

题意:给定一个 n 行 m 列的地牢,其中 ‘.’ 表示可以通行的位置,’X’ 表示不可通行的障碍,牛牛从 (x0 , y0 ) 位置出发,遍历这个地牢,和一般的游戏所不同的是,他每一步只能按照一些指定的步长遍历地牢,要求每一步都不可以超过地牢的边界,也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下,他需要多少步才可以离开这个地牢。

我必须说:出题人是智障!! 谁能看懂这个鬼题目的意思?啊!!
好吧,经过我的WA经验来翻译一下题目:给定一个迷宫,迷宫的出口可以在任何一个’.’上面,现在要让你求最坏情况下的需要移动的次数,如果不能到达出口,输出-1。也就是说在bfs遍历完了之后,还要检查每个’.’,是否能到达!有一个不能到达,答案就是-1

AC代码

#include 
#include 
#include 
#include 
using namespace std;
typedef pair pii;
const int maxn = 50+5;
char mp[maxn][maxn];
int dx[maxn], dy[maxn], dirs;
int d[maxn][maxn];
int n, m, sx, sy;

int bfs() {
    int ans = -1;
    memset(d, -1, sizeof(d));
    queue Q;
    d[sx][sy] = 0;
    Q.push(make_pair(sx, sy));
    while(!Q.empty()) {
        pii f = Q.front(); Q.pop();
        int x = f.first, y = f.second;
        for(int i = 0; i < dirs; i++) {
            int px = x + dx[i];
            int py = y + dy[i];
            if(px < 0 || py = n || py >= m) continue;
            if(mp[px][py] == '.' && d[px][py] == -1) {
                d[px][py] = d[x][y] + 1;
                ans = max(ans, d[px][py]);
                Q.push(make_pair(px, py));
            }
        }
    }
    return ans;
}

int main() {
    while(scanf("%d%d", &n, &m) == 2) {
        for(int i = 0; i < n; i++) {
            scanf("%s", mp[i]);
        }
        scanf("%d%d", &sx, &sy);
        scanf("%d", &dirs);
        for(int i = 0; i < dirs; i++) {
            scanf("%d%d", &dx[i], &dy[i]);
        }
        int ans = bfs();
        bool ok = true;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(mp[i][j] == '.' && d[i][j] == -1) {
                    ok = false;
                    break;
                }
            }
        if(ok) printf("%dn", ans);
        else printf("-1n");
    }
    return 0;
}

如有不当之处欢迎指出!

CSDN博客稿源:CSDN博客 (源链) | 来自的投递 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » 地牢逃脱 (BFS)

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录