【BFS】走迷宫

题目

844. 走迷宫

---

给定一个 $n \times m$ 的二维整数数组，用来表示一个迷宫，数组中只包含 $0$ 或 $1$，其中 $0$ 表示可以走的路，$1$ 表示不可通过的墙壁。

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

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

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行包含 $m$ 个整数（$0$ 或 $1$），表示完整的二维数组迷宫。

输出格式

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

数据范围

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