侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】走迷宫

GabrielxD
2022-10-04 / 0 评论 / 0 点赞 / 16 阅读 / 920 字 / 正在检测是否收录...

题目

信息学奥赛一本通T1252-走迷宫


一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。

给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。

输入格式

第一行是两个整数,R和C,代表迷宫的长和宽。

接下来是R行,每行C个字符,代表整个迷宫。

空地格子用'.'表示,有障碍物的格子用 '#' 表示。

迷宫左上角和右下角都是 '.'

输出格式

输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。

数据范围

1RC401 \le R,C \le 40

输入样例:

5 5
..###
#....
#.#.#
#.#.#
#.#..

输出样例:

9

解题

方法一:BFS

思路

从迷宫的左上角开始广度优先搜索,搜到右下角就停止并返回步数。

代码

import java.util.*;
import java.io.*;

public class Main {
    // 上下左右四个方向
    static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int n, m; // 迷宫的行数和列数
    static char[][] g; // 迷宫中的每一格

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        g = new char[n][m];
        for (int i = 0; i < n; ++i) {
            g[i] = br.readLine().toCharArray();
        }
        System.out.println(bfs());
    }

    static int bfs() {
        // 布尔数组用于标记每个格子是否走过
        boolean[][] vis = new boolean[n][m];
        // 利用队列来进行宽搜 其中的整形数组前两个元素表示格子的坐标 第三个元素表示走到这一格用的步数
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{0, 0, 1}); // 初始化 从左上角开始只走了一步
        vis[0][0] = true; // 表示左上角为已访问
        while (!que.isEmpty()) {
            // 取出队头数组表示的格子
            int[] curr = que.poll();
            int x = curr[0], y = curr[1], step = curr[2];
            // 如果当前格子已经是右下角就直接返回步数
            if (x == n - 1 && y == m - 1) return step;
            // 枚举四个方向
            for (int[] d : DIRECTIONS) {
                // 尝试下一步 算出下一步的格子
                int nx = x + d[0], ny = y + d[1];
                // 如果格子越界或者走到墙里了或者已经走过了 就跳过这一次尝试
                if (nx < 0 || nx >= n || ny < 0 || ny >= m
                    || g[nx][ny] == '#' || vis[nx][ny]) continue;
                // 否则说明这一步是合法的 把它入队并表示其已访问
                que.offer(new int[]{nx, ny, step + 1});
                vis[nx][ny] = true;
            }
        }
        return -1;
    }
}
#include <iostream>
#include <limits>
#include <queue>

using namespace std;

const int MAX_N = 41;
const int DIRECTIONS[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int r, c;
char g[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];

struct State {
    int x, y, step;
};

int bfs() {
    queue<State> que;
    que.push({0, 0, 1});
    vis[0][0] = true;
    while (!que.empty()) {
        State state = que.front();
        que.pop();
        if (state.x == r - 1 && state.y == c - 1) return state.step;
        for (auto d : DIRECTIONS) {
            int nx = state.x + d[0], ny = state.y + d[1];
            if (nx < 0 || nx >= r || ny < 0 || ny >= c ||
                g[nx][ny] == '#' || vis[nx][ny]) continue;
            que.push({nx, ny, state.step + 1});
            vis[nx][ny] = true;
        }
    }

    return -1;
}

int main() {
    scanf("%d%d", &r, &c);
    // 丢弃输入缓存区 不这么做的话字符数组第一行会读到一个空字符
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    for (int i = 0; i < r; ++i) gets(g[i]);
    printf("%d", bfs());

    return 0;
}
0

评论区