侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【BFS】走迷宫

GabrielxD
2022-11-11 / 0 评论 / 0 点赞 / 209 阅读 / 730 字
温馨提示:
本文最后更新于 2022-11-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

844. 走迷宫


给定一个 n×mn \times m 的二维整数数组,用来表示一个迷宫,数组中只包含 0011,其中 00 表示可以走的路,11 表示不可通过的墙壁。

最初,有一个人位于左上角 (1,1)(1, 1) 处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问,该人从左上角移动至右下角 (n,m)(n, m) 处,至少需要移动多少次。

数据保证 (1,1)(1, 1) 处和 (n,m)(n, m) 处的数字为 00,且一定至少存在一条通路。

输入格式

第一行包含两个整数 nnmm

接下来 nn 行,每行包含 mm 个整数(0011),表示完整的二维数组迷宫。

输出格式

输出一个整数,表示从左上角移动至右下角的最少移动次数。

数据范围

1n,m1001 \le n, m \le 100

输入样例:

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例:

8

解题

方法一:BFS

思路

【BFS】走迷宫,使用BFS求解。

代码

#include <iostream>

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, int> PIII;

const int DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int N = 110, M = 1e5 + 10;
int n, m, grid[N][N];
PIII que[M];
int hh, tt = -1;

void bfs() {
    que[++tt] = {{0, 0}, 0};
    grid[0][0] = 1;
    while (hh <= tt) {
        auto pr = que[hh++];
        int x = pr.first.first, y = pr.first.second, step = pr.second;
        if (x == n - 1 && y == m - 1) {
            printf("%d\n", step);
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + DIRS[i][0], ny = y + DIRS[i][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !grid[nx][ny]) {
                que[++tt] = {{nx, ny}, step + 1};
                grid[nx][ny] = 1;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) 
            scanf("%d", &grid[i][j]);
    bfs();
    
    return 0;
}
import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static int n, m;
    static boolean[][] grid;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        grid = new boolean[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                in.nextToken();
                grid[i][j] = in.nval == 0;
            }
        }
        bfs();
    }
    
    static void bfs() {
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{0, 0});
        int step = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                int[] state = que.poll();
                int x = state[0], y = state[1];
                if (x == n - 1 && y == m - 1) {
                    System.out.println(step);
                    return;
                }
                for (int[] DIR : DIRS) {
                    int nx = x + DIR[0], ny = y + DIR[1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny]) {
                        que.offer(new int[]{nx, ny});
                        grid[nx][ny] = false;
                    }
                }
            }
            ++step;
        }
    }
}

0

评论区