【BFS, 剪枝】方格迷宫

题目

4943. 方格迷宫 - AcWing题库

给定一个 $n$ 行 $m$ 列的方格矩阵。

行从上到下依次编号为 $1 \sim n$ ，列从左到右依次编号为 $1 \sim m$ 。

第 $i$ 行第 $j$ 列的方格表示为 $(i,j)$ 。

矩阵中的方格要么是空地（用 . 表示），要么是陷阱（用 # 表示）。

初始时，你位于方格 $(x_1,y_1)$ ，你需要前往方格 $(x_2,y_2)$ 。

每次移动，你可以任选上、下、左、右四个方向之一，并沿该方向移动 $1 \sim k$ 步。

从一个方格移动至相邻方格视为一步。

但是，你要保证在你的移动过程中不能走出矩阵，也不能进入陷阱方格。

请你计算从方格 $(x_1,y_1)$ 移动至方格 $(x_2,y_2)$ ，所需要的最少移动次数。

保证方格 $(x_1,y_1)$ 和方格 $(x_2,y_2)$ 都是空地。

方格 $(x_1,y_1)$ 和方格 $(x_2,y_2)$ 可能是同一个方格。

注意：注意区分本题中移动次数与移动步数的区别。

输入格式

第一行包含三个整数 $n,m,k$ 。

接下来 $n$ 行，每行包含 $m$ 个字符，其中第 $i$ 行第 $j$ 个字符，要么是 .，表示方格 $(i,j)$ 是空地；要么是 #，表示方格 $(i,j)$ 是陷阱。

最后一行包含四个整数 $x_1,y_1,x_2,y_2$ 。

输出格式

一个整数，表示所需要的最少移动次数。

如果无法从方格 $(x_1,y_1)$ 移动至方格 $(x_2,y_2)$ ，则输出 -1。

数据范围

前 $6$ 个测试点满足 $1 \le n,m \le 10$ 。
所有测试点满足 $1 \le n,m,k \le 1000$ ， $1 \le x_1,x_2 \le n$ ， $1 \le y_1,y_2 \le m$ 。

输入样例1：

3 4 4
....
###.
....
1 1 3 1

输出样例1：

输入样例2：

3 4 1
....
###.
....
1 1 3 1

输出样例2：

输入样例3：

2 2 1
.#
#.
1 1 2 2

输出样例3：

-1

解题

方法一：BFS 剪枝

思路

本题是 BFS ，但由于朝一个方向可以走多步，所以需要加特殊的剪枝才能过。

转移状态时，要先枚举方向，在枚举走的步数。

剪枝：

如果向当前方向走到了墙壁或者边界外，直接跳到下一个方向，不再继续枚举当前方向。
关键剪枝：如果转移到的新位置之前已经走过，且比转移过来的位置步数更少，则直接跳到下一个方向（让该方向及该位置周围的状态以更优的状态转移过去）。
原理：想象一下，现在以一个物品为标准做它的复制品，如果发现某一个复制品居然比原品的品质还要好，那么直接抛弃原品，那这个复制品当成新的标准。
如果转移到的位置之前已经走过，就跳过该位置。

代码

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

public class Main {
    static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int m = (int) in.nval;
        in.nextToken(); int k = (int) in.nval;
        char[][] g = new char[n][m];
        for (int i = 0; i < n; ++i) {
            g[i] = br.readLine().toCharArray();
        }
        in.nextToken(); int x1 = (int) in.nval;
        in.nextToken(); int y1 = (int) in.nval;
        in.nextToken(); int x2 = (int) in.nval;
        in.nextToken(); int y2 = (int) in.nval;
        --x1; --y1; --x2; --y2;
        if (x1 == x2 && y1 == y2) {
            System.out.println(0);
            return;
        }
        Queue<int[]> que = new LinkedList<>();
        int[][] steps = new int[n][m];
        for (int[] arr : steps) Arrays.fill(arr, -1);
        que.offer(new int[]{x1, y1});
        steps[x1][y1] = 0;
        while (!que.isEmpty()) {
            int[] curr = que.poll();
            int x = curr[0], y = curr[1], step = steps[x][y];
            for (int[] DIR : DIRS) {
                for (int i = 1; i <= k; ++i) {
                    int nx = x + DIR[0] * i, ny = y + DIR[1] * i;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#') break;
                    if (steps[nx][ny] != -1 && steps[nx][ny] <= step) break;
                    if (steps[nx][ny] != -1) continue;
                    steps[nx][ny] = step + 1;
                    que.offer(new int[]{nx, ny});
                    if (nx == x2 && ny == y2) {
                        System.out.println(steps[nx][ny]);
                        return;
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

目录CONTENT

【BFS, 剪枝】方格迷宫

题目

解题

方法一：BFS 剪枝

思路

代码

评论区