AcWing 1131 拯救大兵瑞恩

题目传送门

一、解题思路

试想下如果本题没有钥匙和门的条件，只要求从左上角走到右下角的最小步数，就是简单的迷宫问题了，可以使用\(BFS\)解决。

加上钥匙和门的的条件，便是类似于八数码问题了。实际上\(BFS\)解决的最短路问题都可以看作求从初始状态到结束状态需要的最小转移次数:
普通迷宫问题的状态就是当前所在的坐标，八数码问题的状态就是当前棋盘的局面。本题在迷宫问题上加上了钥匙和门的条件，显然，处在同一个坐标下，持有钥匙和不持有钥匙就不是同一个状态了，为了能够清楚的表示每个状态，除了当前坐标外还需要加上当前获得的钥匙信息，即f[x][y][st]表示当前处在（x，y）位置下持有钥匙状态为st，将二维坐标压缩成一维就得到f[z][st]这样的状态表示了，或者说，z是格子的编号，从上到下，从左而右的编号依次为1到n*m，st为0110时，表示持有第1,2类钥匙，这里注意我在表示状态时抛弃了最右边的一位，因为钥匙编号从\(1\)开始，我想确定是否持有第\(i\)类钥匙时，只需要判断st >> i & 1是不是等于\(1\)即可。

知道了状态表示，现在题目就转化为了从状态f[1][0]转化为f[n*m][…]状态的最小步数了，我们不关心到达终点是什么状态，只要到达了终点就成功了。

现在进行第二步状态转移，(这里的记录方法就是用PII的记录每个格子，g[PII][PII]的值描述是否有墙)；

• 两个相邻格子间有墙，就不能转移
• 有门，持有该类门钥匙就能转移，没有钥匙就不能转移；
• 没有障碍，正常转移。

下面讨论转移到有钥匙的格子的情况，我们走到有钥匙的格子上，并不用考虑要不要拿钥匙，拿钥匙又不会增加成本，只管拿就行。因此，转移到某个格子时，直接计算下这个格子的状态，格子上有钥匙就在之前状态基础上加上这个钥匙，没有钥匙就继承之前的钥匙状态。

本题看起来复杂，实际上不过是动态规划、\(BFS\)和状态压缩三者的结合，还是比较简单的。

二、实现代码

#include 
using namespace std;
const int N = 105, M = 12;
typedef pair PII;

int g[N][N];              //两个位置之间的间隔是什么，可能是某种门，或者是墙
int key[N];               //某个坐标位置上有哪些钥匙，这是用数位压缩记录的,方便位运算
int d[N][1 << M];         //哪个位置，在携带不同的钥匙情况下的状态
bool st[N][1 << M];       //此状态是否已经走过,用来做bfs的判定
int n, m;                 // n行m列
int p;                    // p类钥匙

//二维转一维的函数
int get(int x, int y) {
    return (x - 1) * m + y; //因为格子是从(1,1)开始到(n,m)的，联想一下八数码
}

int bfs() {
    int dx[] = {-1, 0, 1, 0}; //上右下左
    int dy[] = {0, 1, 0, -1}; //上右下左

    queue q;              // bfs用的队列
    int t = get(1, 1);         //从(1,1)出发
    q.push({t, key[t]});       //位置+携带钥匙的压缩状态
    st[t][key[t]] = true;      //记录此状态已走过
    memset(d, 0x3f, sizeof d); //初始化距离
    d[t][key[t]] = 0;          //初始状态的距离为0

    while (q.size()) {
        PII u = q.front();
        q.pop();
        int z = u.first;  //出发点的一维表示法
        int v = u.second; //钥匙的携带状态
        //四个方向
        for (int i = 0; i < 4; i++) {
            //注意这里我是将格子编号从1开始，因此将其转化为坐标时需要先减一再加一。
            //从0开始编号的话，x = z / m,y = z % m，m是列数；
            //从1开始编号的话x = (z - 1) / m + 1,y = (z - 1) % m + 1，
            //这里从1开始编号的转换特别容易出错。
            int x = (z - 1) / m + dx[i] + 1;
            int y = (z - 1) % m + dy[i] + 1;

            int v1 = v;         //复制出z结点携带过来的钥匙状态
            int z1 = get(x, y); //要去的坐标位置z1
            //出界或有墙
            if (!x || !y || x > n || y > m || !g[z][z1]) continue;
            //有门并且没有这个门的钥匙,那还走什么走
            if (~g[z][z1] && !(v >> g[z][z1] & 1)) continue;
            //走到这个位置，就获得到了这里存在的钥匙(如果有的话)
            v1 |= key[z1];
            //如果这个状态没有走过
            if (!st[z1][v1]) {
                q.push({z1, v1});        //入队列
                st[z1][v1] = true;       //标识上
                d[z1][v1] = d[z][v] + 1; //步数加1
            }
            //找到大兵瑞恩就结束了
            if (z1 == n * m) return d[z1][v1];
        }
    }
    //一直没走到，返回-1
    return -1;
}
int main() {
    cin >> n >> m >> p; // n行m列，p类钥匙
    int k;
    cin >> k; //迷宫中门和墙的总数
    //初始化地图
    memset(g, -1, sizeof g);
    int x1, y1, x2, y2, z, z1, z2;

    while (k--) {
        // z=0:墙
        // z ={1,2,3,4...}哪种类型的门
        cin >> x1 >> y1 >> x2 >> y2 >> z;
        //转化为一维坐标
        z1 = get(x1, y1), z2 = get(x2, y2);
        //记录两个位置之间的间隔是什么
        g[z1][z2] = g[z2][z1] = z;
    }
    //迷宫中存放的钥匙的总数
    int s;
    cin >> s;
    while (s--) {
        cin >> x1 >> y1 >> z;
        //利用状态压缩，描述此位置上有几把钥匙
        key[get(x1, y1)] |= 1 << z;
    }
    cout << bfs() << endl;
    return 0;
}