问题背景

尼莫在深海中迷路了，他的父亲马林需要穿过一个由墙壁和门组成的迷宫去找到他。墙壁的厚度为零，且只能通过门穿过墙壁。马林的目标是找到一条路径，使得穿过门的次数最少。如果马林无法到达尼莫的位置，则输出 -1。

问题分析

1. 迷宫的表示：

   • 迷宫由墙壁和门组成，墙壁可以平行于 X 轴或 Y 轴。
   • 墙壁的左下角坐标为 (x, y)，方向为 d，长度为 t。
   • 门的左下角坐标为 (x, y)，方向为 d，长度固定为 1。

2. 目标：

   • 计算从起点 (0, 0) 到尼莫的位置 (f1, f2) 的最少门数。
   • 如果无法到达，输出 -1。

3. 难点：

   • 如何高效地表示迷宫中的墙壁和门。
   • 如何在迷宫中进行路径搜索，同时记录穿过门的次数。

解题思路

1. 迷宫的初始化：

   • 使用二维数组 xa 和 ya 分别表示水平方向和垂直方向的墙壁。
   • 初始化所有位置为 EMPTY（空），墙壁位置标记为 WALL（无穷大），门位置标记为 DOOR（1）。

2. 路径搜索：

   • 使用广度优先搜索（BFS）算法，从起点 (0, 0) 开始搜索。
   • 使用队列存储待访问的节点，并记录每个节点的最短路径长度。
   • 在搜索过程中，检查每个方向的墙壁或门，并更新路径长度。

3. 边界条件：

   • 如果尼莫的位置超出迷宫范围（f1 或 f2 不在 [1, 199] 内），直接输出 0。
   • 如果无法到达尼莫的位置，输出 -1。

代码实现

#include <iostream>
#include <queue>
#include <cstring> // 用于 memset
#include <cstdio>  // 用于 scanf 和 printf
using namespace std;

#define MAXV 210  // 定义迷宫的最大尺寸
#define INF 1<<29 // 定义无穷大值，用于初始化距离数组

#define EMPTY 0   // 空位置
#define DOOR 1    // 门的位置
#define WALL INF  // 墙壁的位置

// 用于存储迷宫的墙壁和门信息
int xa[MAXV][MAXV], ya[MAXV][MAXV];
// 用于存储从起点到每个位置的最短路径长度
int dis[MAXV][MAXV];
// 四个方向的移动（上、下、左、右）
int dt[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 迷宫的范围
int xmax, ymax;

// 检查坐标是否在迷宫范围内
bool pd(int x, int y) {
    if (x > 0 && x <= xmax && y <= ymax && y > 0) return true;
    return false;
}

// 获取当前位置的墙壁或门的值
int getvalue(int x, int y, int i) {
    if (i == 0) return ya[x - 1][y]; // 上方
    if (i == 1) return ya[x][y];    // 下方
    if (i == 2) return xa[x][y - 1]; // 左方
    return xa[x][y];                // 右方
}

// 广度优先搜索（BFS）算法
int bfs(int tx, int ty) {
    int i, j, vx, vy, dx, dy, tmp;
    queue<int> q;

    // 初始化所有位置的最短路径长度为无穷大
    for (i = 1; i <= ymax; i++) {
        for (j = 1; j <= xmax; j++) {
            dis[i][j] = INF;
        }
    }
    // 起点的最短路径长度为 0
    dis[1][1] = 0;
    q.push(1);
    q.push(1);

    while (!q.empty()) {
        vx = q.front(); q.pop();
        vy = q.front(); q.pop();

        for (i = 0; i < 4; i++) {
            dx = vx + dt[i][0];
            dy = vy + dt[i][1];
            tmp = getvalue(vx, vy, i); // 获取当前位置的墙壁或门的值
            if (pd(dx, dy) && dis[dx][dy] > dis[vx][vy] + tmp) {
                dis[dx][dy] = dis[vx][vy] + tmp; // 更新最短路径长度
                q.push(dx);
                q.push(dy);
            }
        }
    }

    // 如果无法到达目标位置，返回 -1
    return (dis[tx][ty] == INF ? -1 : dis[tx][ty]);
}

int main() {
    int n, m, i, j;
    int x, y, d, t;
    double sx, sy;

    // 处理多个测试用例，直到遇到 -1 -1
    while (scanf("%d%d", &m, &n)) {
        if (m == -1 && n == -1) break;

        ymax = xmax = -1; // 初始化迷宫范围
        memset(xa, EMPTY, sizeof(xa)); // 初始化水平方向的墙壁信息
        memset(ya, EMPTY, sizeof(ya)); // 初始化垂直方向的墙壁信息

        // 读取墙壁信息
        for (i = 0; i < m; i++) {
            scanf("%d%d%d%d", &x, &y, &d, &t);
            if (d) {
                for (j = 0; j < t; j++) ya[x][y + j + 1] = WALL; // 标记垂直墙壁
                ymax = max(y + t + 1, ymax); // 更新迷宫的垂直范围
                xmax = max(x + 1, xmax);     // 更新迷宫的水平范围
            } else {
                for (j = 0; j < t; j++) xa[x + j + 1][y] = WALL; // 标记水平墙壁
                ymax = max(y + 1, ymax);     // 更新迷宫的垂直范围
                xmax = max(x + t + 1, xmax); // 更新迷宫的水平范围
            }
        }

        // 读取门的信息
        for (i = 0; i < n; i++) {
            scanf("%d%d%d", &x, &y, &d);
            if (d) ya[x][y + 1] = DOOR; // 标记垂直方向的门
            else xa[x + 1][y] = DOOR;   // 标记水平方向的门
        }

        // 读取尼莫的位置
        scanf("%lf%lf", &sx, &sy);

        // 检查尼莫的位置是否在迷宫范围内
        if (!(sx >= 1 && sx <= 199 && sy >= 1 && sy <= 199)) {
            printf("0\n"); // 如果不在范围内，输出 0
        } else {
            // 计算从起点到尼莫位置的最少门数
            printf("%d\n", bfs((int)sx + 1, (int)sy + 1));
        }
    }
    return 0;
}

代码说明

1. 迷宫的初始化：

   • 使用 memset 将 xa 和 ya 初始化为 EMPTY。
   • 根据输入的墙壁信息，将对应的 xa 或 ya 设置为 WALL。
   • 根据输入的门信息，将对应的 xa 或 ya 设置为 DOOR。

2. 广度优先搜索：

   • 使用队列存储待访问的节点。
   • 在搜索过程中，检查每个方向的墙壁或门，并更新路径长度。
   • 如果到达目标位置，返回路径长度；否则返回 -1。

3. 边界条件：

   • 如果尼莫的位置超出迷宫范围，直接输出 0。

总结

本题通过广度优先搜索算法，结合迷宫的墙壁和门的表示，高效地求解了马林营救尼莫的最少门数问题。代码逻辑清晰，易于理解和实现。