【BFS】走迷宫

题目

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

---

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

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

输入格式

第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。

接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。

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

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

输出格式

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

数据范围

$1 \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;
}