侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【BFS, 剪枝】方格迷宫

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

题目

4943. 方格迷宫 - AcWing题库


给定一个 nnmm 列的方格矩阵。

行从上到下依次编号为 1n1 \sim n ,列从左到右依次编号为 1m1 \sim m

ii 行第 jj 列的方格表示为 (i,j)(i,j)

矩阵中的方格要么是空地(用 . 表示),要么是陷阱(用 # 表示)。

初始时,你位于方格 (x1,y1)(x_1,y_1) ,你需要前往方格 (x2,y2)(x_2,y_2)

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

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

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

请你计算从方格 (x1,y1)(x_1,y_1) 移动至方格 (x2,y2)(x_2,y_2) ,所需要的最少移动次数

保证方格 (x1,y1)(x_1,y_1) 和方格 (x2,y2)(x_2,y_2) 都是空地。

方格 (x1,y1)(x_1,y_1) 和方格 (x2,y2)(x_2,y_2) 可能是同一个方格。

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

输入格式

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

接下来 nn 行,每行包含 mm 个字符,其中第 ii 行第 jj 个字符,要么是 .,表示方格 (i,j)(i,j) 是空地;要么是 #,表示方格 (i,j)(i,j) 是陷阱。

最后一行包含四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2

输出格式

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

如果无法从方格 (x1,y1)(x_1,y_1) 移动至方格 (x2,y2)(x_2,y_2) ,则输出 -1

数据范围

66 个测试点满足 1n,m101 \le n,m \le 10
所有测试点满足 1n,m,k10001 \le n,m,k \le 10001x1,x2n1 \le x_1,x_2 \le n1y1,y2m1 \le y_1,y_2 \le m

输入样例1:

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

输出样例1:

3

输入样例2:

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

输出样例2:

8

输入样例3:

2 2 1
.#
#.
1 1 2 2

输出样例3:

-1

解题

方法一:BFS 剪枝

思路

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

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

剪枝:

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

代码

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);
    }
}
0

评论区