ID: 20

Difficulty: 6

题目内容

小红是一名勇敢的冒险家，他一直梦想着找到传说中的黄金之城。他听说在一个遥远的沙漠中，有一个隐藏着无数宝藏的迷宫，只有最聪明和最勇敢的人才能进入并找到出路。小红决定去挑战这个迷宫，他带着一张地图和一些装备，踏上了寻宝之旅。

但是，这个迷宫并不是那么容易通过的，它充满了各种危险和难题。除了一些隐藏在地面上的陷阱之外，还有一些时隐时现的墙壁，它们会随机地出现和消失，阻挡小红的前进。小红必须小心地观察墙壁的状态循环，绕过陷阱和墙壁，或者等待合适的时机通过。这是个 $n\times n$ 大小的迷宫，迷宫中存在着 $k$ 个陷阱，并且每个位置都存在着一个墙壁的状态循环，状态循环以 $3$ 个单位时间作为一个循环， $0$ 表示没有墙壁， $1$ 表示有墙壁。

小红在每个单位时间可以向上、下、左、右某个方向移动一个地图单位,当然也可以选择原地踏步。

限制:如果小红移动方向上有陷阱，或者小红移动目的地在下一个单位时间出现墙壁，则不可以朝该方向移动，同时，如果小红当前位置在下一个单位时间会出现墙壁，那小红也不可以选择停在原地。

我们需要计算出小红找到宝藏的最短时间。注意，小红可能并到不了目的地哦，这种情况输出-1

输入描述

输入第一行为一个整数 $n$ ，表示迷宫的大小。（ $2<= n <= 100$ )

输入第二行为一个整数 $k$ ，表示迷宫中陷阱的数量。（ $0<k <= n\times n-2$ ）

接下来输入一行 $2\times k$ 个整数,具体为 $row_1\ col_1\ row_2\ col_2\ ...\ row_k\ col_k$ ，表示位置( $row_i$ , $col_i$ )存在一个陷阱。

接下来一行为两对整数（ $row1$ , $col1$ ) 和 ( $row2$ , $col2$ )，表示宝藏的位置和小红的起始位置。

然后接下来 $n$ 行: 每行 $n$ 个字符串空格分开，每个字符串长度固定为 $3$ ，内容固定只有 $0$ 和 $1$ ，表示每个位置的墙壁的状态循环。

注意：地图左上角为(0,0)，输入保证所有位置合法

输出描述

输出一个整数，表示小红找到宝藏的最短时间。

样例

样例一

输入

3
2
1 0 1 2
2 1 2 0
100 100 100
100 000 100
000 000 001

输出

样例解释

小红最快的移动顺序： [2,0] ->[2,1]

样例二

输入

3
2
1 0 2 0
0 1 2 2
000 000 001
010 101 101
110 010 000

输出

样例解释

小红最快的移动顺序： [2,2] ->[1,2] ->[2,2] ->[2,1] ->[1,1] ->[0,1]

题面描述

塔子哥是一名勇敢的冒险家，他梦想找到传说中的黄金之城。在一个充满陷阱和随机出现墙壁的 $n * n$ 大小的迷宫中，他需要巧妙地避开这些障碍，才能找到宝藏。迷宫中有 $k$ 个陷阱，每个位置的墙壁状态以 $3$ 个单位时间循环变化，塔子哥每个单位时间可以选择移动或原地不动，但不能停在有墙壁或陷阱的位置。我们需要计算他找到宝藏的最短时间，如果无法到达宝藏，则输出 -1。

题解

塔子哥的迷宫挑战可以用广度优先搜索（BFS）来解决，但与普通的最短路径问题不同，本题涉及到一个状态维度，即墙壁的状态在时间上是周期性变化的。每个位置在每个时间单位可能会有不同的墙壁状态，因此我们需要使用三维数组来表示距离。

我们定义一个三维数组 dist[i][j][k]，表示到达坐标 (i, j) 且状态为 k 的最短时间。状态 k 的取值为 0, 1, 2，对应于时间的三个状态循环。每次移动时，塔子哥可以选择向四个方向移动，或选择原地不动，这种情况下，状态会随时间变化。

在判断能否移动到某个位置时，我们不仅要检查该位置是否有陷阱，还要检查目标位置在下一时间单位的墙壁状态，以确保塔子哥能够顺利通过。

代码分析

这段代码实现了在一个迷宫中寻找从起始位置到目标位置的最短路径，考虑了陷阱和周期性变化的墙壁状态。以下是关键点：

1. 数据结构

dist[N][N][3]: 三维数组，用于存储到达 (i, j) 位置且状态为 k 的最短时间。
g[N][N]: 标记陷阱的位置。
state[N][N]: 存储每个位置的墙壁状态（字符串形式）。

2. BFS 函数

初始化: 将 dist 数组设为无穷大，起始位置的距离设为 0，并将其加入队列。
主循环:
- 从队列中取出节点，检查是否到达目标位置。
- 遍历五个移动方向，计算新位置和时间。
- 检查是否越界、是否有陷阱以及墙壁状态。
更新最短距离: 如果新位置可达且更新了最短路径，则记录并将新状态加入队列。

C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1010;  // 定义最大迷宫大小
int dx[5] = {-1, 1, 0, 0, 0};  // 方向数组，表示上下左右和原地不动
int dy[5] = {0, 0, 1, -1, 0};  
int dist[N][N][3];  // 三维数组，存储到达 (x, y) 状态为 z 的最小距离
bool g[N][N];  // 标记陷阱的位置
string state[N][N];  // 存储每个位置的墙壁状态
int n, k, sx, sy, ex, ey;  // n 为迷宫大小，k 为陷阱数量，sx, sy 为起始位置，ex, ey 为目标位置

struct node {
    int x, y, time;  // 定义节点结构，包含坐标和当前时间
};

// BFS 函数实现
int bfs() {
    memset(dist, 0x3f, sizeof dist);  // 初始化距离数组为无穷大
    dist[sx][sy][0] = 0;  // 起始位置的时间状态为 0 的距离为 0
    queue<node> q;  // 定义队列用于 BFS
    q.push({sx, sy, 0});  // 将起始位置加入队列

    while (!q.empty()) {  // 当队列不为空时
        auto t = q.front();  // 获取队头元素
        q.pop();  // 弹出队头元素

        // 如果到达目标位置，返回当前时间
        if (t.x == ex && t.y == ey) return t.time;

        int x = t.x, y = t.y, time = t.time;  // 当前位置和时间
        for (int i = 0; i < 5; i++) {  // 遍历所有可能的移动方向
            int a = dx[i] + x, b = dy[i] + y;  // 计算目标位置
            int next_time = time + 1;  // 增加时间

            // 检查目标位置是否越界，是否有陷阱，或者是否有墙壁
            if (a < 0 || a >= n || b < 0 || b >= n || g[a][b] || state[a][b][next_time % 3] == '1') 
                continue;  // 不满足条件则跳过

            // 更新最短距离
            if (dist[a][b][next_time % 3] > dist[x][y][time % 3] + 1) {
                dist[a][b][next_time % 3] = dist[x][y][time % 3] + 1;  // 更新距离
                q.push({a, b, next_time});  // 将新状态加入队列
            }
        }
    }
    return -1;  // 如果无法到达目标位置，返回 -1
}

int main() {
    cin >> n >> k;  // 读取迷宫大小和陷阱数量
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;  // 读取陷阱位置
        g[a][b] = true;  // 标记陷阱
    }

    cin >> ex >> ey >> sx >> sy;  // 读取起始和目标位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> state[i][j];  // 读取每个位置的墙壁状态
        }
    }
    
    cout << bfs() << endl;  // 调用 BFS 函数并输出结果
    return 0;
}

Java

import java.util.*;

// 定义节点类，包含坐标和当前时间
class Node {
    int x, y, time;  // x 和 y 为坐标，time 为当前时间

    // 构造函数
    Node(int x, int y, int time) {
        this.x = x;  // 初始化坐标 x
        this.y = y;  // 初始化坐标 y
        this.time = time;  // 初始化时间
    }
}

public class Main {
    static final int N = 1010;  // 定义最大迷宫大小
    // 定义移动方向：上、下、右、左、原地不动
    static int[] dx = {-1, 1, 0, 0, 0}, dy = {0, 0, 1, -1, 0};
    static int[][][] dist = new int[N][N][3];  // 三维数组，存储最短路径
    static boolean[][] g = new boolean[N][N];  // 标记陷阱位置
    static String[][] state = new String[N][N];  // 存储每个位置的墙壁状态
    static int n, k, sx, sy, ex, ey;  // n 为迷宫大小，k 为陷阱数量，sx, sy 为起始位置，ex, ey 为目标位置

    // BFS 函数实现
    static int bfs() {
        // 初始化距离数组为最大值
        for (int[][] row : dist) {
            for (int[] col : row) {
                Arrays.fill(col, Integer.MAX_VALUE);
            }
        }
        // 起始位置的状态距离设为 0
        dist[sx][sy][0] = 0;  
        Queue<Node> queue = new LinkedList<>();  // 定义队列用于 BFS
        queue.offer(new Node(sx, sy, 0));  // 将起始位置加入队列

        // BFS 主循环
        while (!queue.isEmpty()) {
            Node t = queue.poll();  // 从队列中取出一个节点
            // 如果到达目标位置，返回当前时间
            if (t.x == ex && t.y == ey) return t.time;  

            int x = t.x, y = t.y, time = t.time;  // 获取当前节点的坐标和时间
            // 遍历所有可能的移动方向
            for (int i = 0; i < 5; i++) {
                int a = dx[i] + x, b = dy[i] + y, next_time = time + 1;  // 计算新位置和下一时间
                // 检查新位置是否越界、是否有陷阱或墙壁
                if (a < 0 || a >= n || b < 0 || b >= n || g[a][b] || state[a][b].charAt(next_time % 3) == '1') continue;

                // 更新最短距离
                if (dist[a][b][next_time % 3] > dist[x][y][time % 3] + 1) {
                    dist[a][b][next_time % 3] = dist[x][y][time % 3] + 1;  // 记录新位置的最短路径
                    queue.offer(new Node(a, b, next_time));  // 将新状态加入队列
                }
            }
        }
        return -1;  // 如果无法到达目标位置，返回 -1
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  // 创建 Scanner 对象读取输入
        n = sc.nextInt();  // 读取迷宫的大小
        k = sc.nextInt();  // 读取陷阱的数量
        // 读取陷阱的位置并标记
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            g[a][b] = true;  // 标记陷阱
        }
        // 读取目标位置和起始位置
        ex = sc.nextInt();
        ey = sc.nextInt();
        sx = sc.nextInt();
        sy = sc.nextInt();
        // 读取每个位置的墙壁状态
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                state[i][j] = sc.next();
        
        // 调用 BFS 函数并输出结果
        System.out.println(bfs());
    }
}

Python3

from collections import deque  # 导入双端队列，用于 BFS
from sys import maxsize  # 导入最大整数值，用于初始化距离

N = 1010  # 定义最大迷宫大小
dx = [-1, 1, 0, 0, 0]  # 移动方向数组：上、下、右、左、原地不动
dy = [0, 0, 1, -1, 0]  # 移动方向数组
# 三维数组，dist[i][j][k] 表示到达 (i, j) 且状态为 k 的最短时间
dist = [[[maxsize]*3 for _ in range(N)] for _ in range(N)]
g = [[False]*N for _ in range(N)]  # 布尔数组，标记陷阱的位置
state = [['']*N for _ in range(N)]  # 二维数组，存储每个位置的墙壁状态
n, k, sx, sy, ex, ey = 0, 0, 0, 0, 0, 0  # 初始化迷宫大小、陷阱数量和坐标

def bfs():
    # 初始化距离数组为最大值
    for row in dist:
        for col in row:
            col[:] = [maxsize]*3
    # 设置起始位置的状态距离为 0
    dist[sx][sy][0] = 0
    queue = deque([(sx, sy, 0)])  # 初始化队列，将起始位置加入队列
    while queue:  # 当队列不为空时
        x, y, time = queue.popleft()  # 弹出队头元素
        # 如果到达目标位置，返回当前时间
        if x == ex and y == ey: 
            return time  
        # 遍历所有可能的移动方向
        for i in range(5):
            # 计算新位置和下一个时间
            a, b, next_time = dx[i] + x, dy[i] + y, time + 1
            # 检查新位置是否越界、是否有陷阱或墙壁
            if a < 0 or a >= n or b < 0 or b >= n or g[a][b] or state[a][b][next_time % 3] == '1':
                continue
            # 更新最短距离
            if dist[a][b][next_time % 3] > dist[x][y][time % 3] + 1:
                dist[a][b][next_time % 3] = dist[x][y][time % 3] + 1  # 记录新位置的最短路径
                queue.append((a, b, next_time))  # 将新状态加入队列
    return -1  # 如果无法到达目标位置，返回 -1

if __name__ == "__main__":
    n = int(input())  # 读取迷宫的大小
    k = int(input())  # 读取陷阱的数量
    traps = list(map(int, input().split()))  # 读取陷阱的位置
    # 标记陷阱的位置
    for i in range(0, len(traps), 2):
        g[traps[i]][traps[i+1]] = True
    # 读取目标位置和起始位置
    ex, ey, sx, sy = map(int, input().split())
    # 读取每个位置的墙壁状态
    for i in range(n):
        state[i] = list(input().split())
    # 调用 BFS 函数并输出结果
    print(bfs())

#P1572. 2023.05.06-暑期实习-第三题-黄金之城寻宝

2023.05.06-暑期实习-第三题-黄金之城寻宝