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

TaZi SU @ 8 months ago

题面描述

塔子哥是一名勇敢的冒险家，他梦想找到传说中的黄金之城。在一个充满陷阱和随机出现墙壁的 $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())

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

题面描述

题解

代码分析

1. 数据结构

2. BFS 函数

Information

Status

Development

Support