题解 ：

问题分析

这是一个带状态的最短路搜索问题。麦克需要从(1,1)走到(n,m)，途中可以收集钥匙来打开对应类型的门。钥匙可以重复使用，且拾取钥匙不需要时间。

关键点：

1. 网格大小为 $n \times m$ ($n,m$ 通常不大)
2. 门有 $p$ 种类型 ($p \leq 10$)
3. 钥匙可以打开对应类型的门
4. 墙完全不能通过

算法思路：状态压缩BFS

由于 $p \leq 10$，我们可以使用状态压缩来表示当前拥有的钥匙集合。用整数的二进制位表示是否拥有某类钥匙（第 $i$ 位为1表示拥有第 $i$ 类钥匙）。

状态定义：(x, y, key_state) 表示在位置(x,y)且拥有钥匙状态为key_state

使用BFS搜索从(1,1,0)到(n,m,*)（任意钥匙状态）的最短路径。

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 11  // 根据题目实际范围调整
#define MAX_M 11
#define MAX_P 11
#define MAX_STATE (1 << 10)  // 2^10 = 1024

// 方向：上、右、下、左
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

typedef struct {
    int x, y;
    int keys;      // 钥匙状态（二进制压缩）
    int steps;     // 已走步数
} State;

typedef struct {
    int front, rear;
    State data[MAX_N * MAX_M * MAX_STATE];
} Queue;

void init_queue(Queue *q) {
    q->front = q->rear = 0;
}

bool is_empty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, State s) {
    q->data[q->rear++] = s;
}

State dequeue(Queue *q) {
    return q->data[q->front++];
}

int main() {
    int n, m, p;
    scanf("%d %d %d", &n, &m, &p);
    
    int k;
    scanf("%d", &k);
    
    // 存储边的情况：-1表示墙，0表示通路，>0表示需要对应类型的钥匙
    // door[x1][y1][x2][y2] 表示从(x1,y1)到(x2,y2)的边
    // 由于n,m可能较大，使用三维数组存储每个点的四个方向
    int door[MAX_N][MAX_M][4];
    memset(door, -1, sizeof(door));
    
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2, g;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &g);
        
        // 确定方向
        int dir = -1;
        if (x1 == x2) {
            if (y1 + 1 == y2) dir = 1;  // 向右
            else if (y1 - 1 == y2) dir = 3;  // 向左
        } else if (y1 == y2) {
            if (x1 + 1 == x2) dir = 2;  // 向下
            else if (x1 - 1 == x2) dir = 0;  // 向上
        }
        
        if (dir != -1) {
            // 双向设置
            door[x1][y1][dir] = g;
            // 反方向
            int opp_dir = (dir + 2) % 4;
            door[x2][y2][opp_dir] = g;
        }
    }
    
    int s;
    scanf("%d", &s);
    
    // 存储每个位置的钥匙
    int cell_keys[MAX_N][MAX_M] = {0};
    
    for (int i = 0; i < s; i++) {
        int x, y, q;
        scanf("%d %d %d", &x, &y, &q);
        // 使用二进制位存储钥匙，q从1开始，需要减1
        cell_keys[x][y] |= (1 << (q - 1));
    }
    
    // BFS
    bool visited[MAX_N][MAX_M][MAX_STATE];
    memset(visited, 0, sizeof(visited));
    
    Queue q;
    init_queue(&q);
    
    // 起始状态
    State start = {1, 1, cell_keys[1][1], 0};  // 拾取起点钥匙
    visited[1][1][start.keys] = true;
    enqueue(&q, start);
    
    int result = -1;
    
    while (!is_empty(&q)) {
        State current = dequeue(&q);
        
        // 到达终点
        if (current.x == n && current.y == m) {
            result = current.steps;
            break;
        }
        
        // 尝试四个方向
        for (int dir = 0; dir < 4; dir++) {
            int nx = current.x + dx[dir];
            int ny = current.y + dy[dir];
            
            // 检查边界
            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }
            
            // 检查是否可以通行
            int door_type = door[current.x][current.y][dir];
            
            if (door_type == -1) {
                continue;  // 没有边（初始化值）
            } else if (door_type == 0) {
                continue;  // 墙，不能通过
            } else if (door_type > 0) {
                // 门，需要对应钥匙
                int key_needed = 1 << (door_type - 1);
                if ((current.keys & key_needed) == 0) {
                    continue;  // 没有钥匙
                }
            }
            // door_type == -1（初始值）表示通路
            
            // 新位置
            int new_keys = current.keys | cell_keys[nx][ny];
            
            // 检查是否访问过
            if (!visited[nx][ny][new_keys]) {
                visited[nx][ny][new_keys] = true;
                State next = {nx, ny, new_keys, current.steps + 1};
                enqueue(&q, next);
            }
        }
    }
    
    printf("%d\n", result);
    
    return 0;
}

算法优化版本

上面的代码为了清晰展示了算法思想，但door数组是四维的，可能占用较大内存。以下是优化版本：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 105  // 更大的范围
#define MAX_M 105
#define MAX_P 11
#define MAX_STATE (1 << 10)

typedef struct {
    int x, y, keys, steps;
} State;

typedef struct Node {
    int x, y, keys, steps;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

void init_queue(Queue* q) {
    q->front = q->rear = NULL;
}

bool is_empty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, int x, int y, int keys, int steps) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->x = x;
    new_node->y = y;
    new_node->keys = keys;
    new_node->steps = steps;
    new_node->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
}

State dequeue(Queue* q) {
    Node* temp = q->front;
    State s = {temp->x, temp->y, temp->keys, temp->steps};
    
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    return s;
}

void free_queue(Queue* q) {
    while (!is_empty(q)) {
        dequeue(q);
    }
}

int main() {
    int n, m, p;
    scanf("%d %d %d", &n, &m, &p);
    
    int k;
    scanf("%d", &k);
    
    // 使用二维数组的二维数组存储门信息
    // wall[x][y][dir] = g: 从(x,y)向dir方向的门类型
    int*** wall = (int***)malloc((n + 2) * sizeof(int**));
    for (int i = 0; i <= n + 1; i++) {
        wall[i] = (int**)malloc((m + 2) * sizeof(int*));
        for (int j = 0; j <= m + 1; j++) {
            wall[i][j] = (int*)malloc(4 * sizeof(int));
            for (int d = 0; d < 4; d++) {
                wall[i][j][d] = -1;  // 初始为-1表示通路
            }
        }
    }
    
    for (int i = 0; i < k; i++) {
        int x1, y1, x2, y2, g;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &g);
        
        // 确定方向
        if (x1 == x2) {
            if (y1 < y2) {
                wall[x1][y1][1] = g;  // 向右
                wall[x2][y2][3] = g;  // 向左
            } else {
                wall[x1][y1][3] = g;  // 向左
                wall[x2][y2][1] = g;  // 向右
            }
        } else {  // y1 == y2
            if (x1 < x2) {
                wall[x1][y1][2] = g;  // 向下
                wall[x2][y2][0] = g;  // 向上
            } else {
                wall[x1][y1][0] = g;  // 向上
                wall[x2][y2][2] = g;  // 向下
            }
        }
    }
    
    int s;
    scanf("%d", &s);
    
    // 存储每个位置的钥匙
    int** cell_keys = (int**)malloc((n + 2) * sizeof(int*));
    for (int i = 0; i <= n + 1; i++) {
        cell_keys[i] = (int*)calloc((m + 2), sizeof(int));
    }
    
    for (int i = 0; i < s; i++) {
        int x, y, q;
        scanf("%d %d %d", &x, &y, &q);
        cell_keys[x][y] |= (1 << (q - 1));
    }
    
    // BFS
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    // 访问标记
    bool*** visited = (bool***)malloc((n + 2) * sizeof(bool**));
    for (int i = 0; i <= n + 1; i++) {
        visited[i] = (bool**)malloc((m + 2) * sizeof(bool*));
        for (int j = 0; j <= m + 1; j++) {
            visited[i][j] = (bool*)calloc(MAX_STATE, sizeof(bool));
        }
    }
    
    Queue q;
    init_queue(&q);
    
    // 起始状态
    int start_keys = cell_keys[1][1];
    visited[1][1][start_keys] = true;
    enqueue(&q, 1, 1, start_keys, 0);
    
    int result = -1;
    
    while (!is_empty(&q)) {
        State current = dequeue(&q);
        
        // 到达终点
        if (current.x == n && current.y == m) {
            result = current.steps;
            break;
        }
        
        // 尝试四个方向
        for (int dir = 0; dir < 4; dir++) {
            int nx = current.x + dx[dir];
            int ny = current.y + dy[dir];
            
            // 检查边界
            if (nx < 1 || nx > n || ny < 1 || ny > m) {
                continue;
            }
            
            // 检查是否可以通行
            int door_type = wall[current.x][current.y][dir];
            
            if (door_type == 0) {
                continue;  // 墙，不能通过
            } else if (door_type > 0) {
                // 门，需要对应钥匙
                int key_needed = 1 << (door_type - 1);
                if ((current.keys & key_needed) == 0) {
                    continue;  // 没有钥匙
                }
            }
            // door_type == -1 或 >0且有钥匙 表示可以通行
            
            // 新位置
            int new_keys = current.keys | cell_keys[nx][ny];
            
            // 检查是否访问过
            if (!visited[nx][ny][new_keys]) {
                visited[nx][ny][new_keys] = true;
                enqueue(&q, nx, ny, new_keys, current.steps + 1);
            }
        }
    }
    
    printf("%d\n", result);
    
    // 释放内存
    free_queue(&q);
    
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            free(wall[i][j]);
            free(visited[i][j]);
        }
        free(wall[i]);
        free(visited[i]);
        free(cell_keys[i]);
    }
    free(wall);
    free(visited);
    free(cell_keys);
    
    return 0;
}

算法详细解释

1. 状态表示

• 位置：(x, y) 坐标
• 钥匙状态：用整数 keys 的二进制位表示
  • 第 i 位为1表示拥有第 i+1 类钥匙
  • 例如：keys = 5 (二进制 0101) 表示拥有第1类和第3类钥匙

2. 门和墙的存储

使用三维数组 wall[x][y][dir]：

• -1：通路（默认值）
• 0：墙
• >0：需要对应类型钥匙的门

3. BFS搜索过程

从起点 (1,1) 开始，初始钥匙为起点位置的钥匙。

对于每个状态 (x, y, keys)：

1. 如果到达终点 (n,m)，返回步数
2. 尝试四个方向移动
3. 检查移动是否合法：
   • 不越界
   • 不是墙
   • 如果是门，需要对应钥匙
4. 移动到新位置后，拾取新位置的钥匙
5. 如果新状态 (nx, ny, new_keys) 未访问过，加入队列

4. 复杂度分析

• 状态数：$O(n \times m \times 2^p)$
• 每个状态扩展4个方向
• 总复杂度：$O(4 \times n \times m \times 2^p)$
• 对于 $n,m \leq 50, p \leq 10$ 是可接受的

关键点注意

1. 钥匙拾取：移动到新格子时，立即拾取该格子的所有钥匙
2. 状态去重：相同的 (x,y,keys) 状态只需访问一次
3. 门和墙的区别：
   • 墙（g=0）：完全不能通过
   • 门（g>0）：需要对应钥匙才能通过
4. 多钥匙处理：一个格子可能有多把不同类型的钥匙

样例验证

对于题目样例：

4 4 9
9
1 2 1 3 2    # (1,2)-(1,3): 门2
1 2 2 2 0    # (1,2)-(2,2): 墙
...（其他边）
2            # 2把钥匙
2 1 2        # (2,1): 钥匙2
4 2 1        # (4,2): 钥匙1

算法会找到最短路径，输出14。

进一步优化

对于更大的网格，可以考虑：

1. 使用双向BFS
2. 使用A*搜索启发式
3. 使用位运算优化钥匙状态处理

这个算法是解决此类问题的标准方法，正确且高效。