孤岛营救问题

2024-02-10 18:30:34

孤岛营救问题

题目描述

$1944$年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为$N$行，东西方向被划分为$M$列，于是整个迷宫被划分为$N\times M$个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的 $22$个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成$P$类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即$(N,M)$单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入$(1,1)$单元。另外，麦克从一个单元移动到另一个相邻单元的时间为$1$，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

输入输出格式

输入格式：

第$1$行有$3$个整数，分别表示$N,M,P$的值。

第$2$行是$1$个整数$K$，表示迷宫中门和墙的总数。

第$I+2$行$(1\leq I\leq K)$，有$5$个整数，依次为$X_{i1},Y_{i1},X_{i2},Y_{i2},G_i$：

当$G_i \geq 1$时，表示$(X_{i1},Y_{i1})$单元与$(X_{i2},Y_{i2})$单元之间有一扇第$G_i$类的门
当$G_i=0$时，表示$(X_{i1},Y_{i1})$单元与$(X_{i2},Y_{i2})$单元之间有一堵不可逾越的墙（其中，$|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1$，$0\leq G_i\leq P$）。

第$K+3$行是一个整数$S$，表示迷宫中存放的钥匙总数。

第$K+3+J$行$(1\leq J\leq S)$，有$3$个整数，依次为$X_{i1},Y_{i1},Q_i$：表示第$J$把钥匙存放在$(X_{i1},Y_{i1})$单元里，并且第$J$把钥匙是用来开启第$Q_i$类门的。（其中$1\leq Q_i\leq P$）。

输入数据中同一行各相邻整数之间用一个空格分隔。

输出格式：

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出$ -1$。

输入输出样例

输入样例

输出样例

说明

$|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1,0\leq G_i\leq P∣$

$1\leq Q_i\leq P$

$N,M,P\leq10, K<150,S\leq 14$

$Solution$

观察到数据范围很小，可以状压。

对钥匙状压，记录每个点的最短时间和相应的钥匙，然后广搜就好了。

似乎没有什么好说的。代码详解。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
long long read(){
    long long x = 0; int f = 0; char c = getchar();
    while(c < '0' || c > '9') f |= c == '-', c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f? -x:x;
}

int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};//记录方向
int n, m, p, k, a, b, c, d, e;
int key[22][22], wall[22][22][4], vis[1024][22][22];
    //每个点的钥匙   墙的状态       是否访问过
struct szh{
    int key, x, y, d;//广搜结构体
};
queue<szh> q;
int main(){
    n = read(); m = read(); p = read(); k = read();
    while(k--){
        a = read(); b = read(); c = read(); d = read(); e = read();
        if(!e--) e = 11;//墙特殊处理
        for(int i = 0; i < 4; i++)//找方向
            if(c == a + dir[i][0] && d == b + dir[i][1]){
                wall[a][b][i] = 1 << e,wall[c][d][i ^ 1] = 1 << e;//两个点都要更新
                break;
            }
    }
    k = read();
    while(k--){
        a = read(); b = read(); c = read();
        key[a][b] |= 1 << (c - 1);//状压钥匙
    }
    q.push((szh){key[1][1], 1, 1, 0});//起点入队
    while(!q.empty()){
        szh u = q.front(); q.pop();
        int ky = u.key, x = u.x, y = u.y, d = u.d;
        if(x == n && y == m){//走到终点就退出
            printf("%d\n", d);return 0;
        }
        for(int i = 0; i < 4; i++){//遍历四个方向
            if((wall[x][y][i] & ky) != wall[x][y][i]) continue;//没对应钥匙
            int nx = x + dir[i][0], ny = y + dir[i][1], nky = ky | key[nx][ny];
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue;//越界
            if(!vis[nky][nx][ny])//入队
                vis[nky][nx][ny] = 1, q.push((szh){nky, nx, ny, d + 1});
        }
    }
    puts("-1");
    return 0;
}

码农公寓

孤岛营救问题