AcWing1131. 拯救大兵瑞恩

2022-12-23 23:06:54 来源：博客园

(资料图)

题目传送门

解题思路

\(\qquad\)我们可以用一个状态压缩的思路，对于所有的钥匙，用来开第\(i\)类门的我们把这把钥匙放到从右往左数的第\(i\)位（这里是为了方便写，比如开第\(1\)种门的\(key[x][y] |= 1 << 1\)），这样我们在判断是否有钥匙的时候只要用到\(x\) >> \(i\) \(\ \& \ 1\)这样取二进制位下第\(i\)位的方法就行了。\(\qquad\)钥匙处理完了，距离我们应该怎么判断呢？可以看出这其实是求从\((1,1)到(n,m)\)的最短路，而且边权是\(1\)（这里不能走的路我们都不建边），这样的路上，最短距离是可以用\(BFS\)求的\(\qquad\)关于处理能否走的路的几种判断\(\qquad\)\(1.\)扩展的点坐标越界，也就是\(x<1\), \(x>n\), \(y<1\), \(y>m\)任意一种情况发生时，不能走，\(continue\)掉\(\qquad\)\(2.\)遇到不可逾越的墙，顾名思义，不能走，\(continue\)掉\(\qquad\)\(3.\)遇到有门要开时(\(g[t.x][t.y][nex][ney] > 0\))，判断是否有对应的钥匙，这个钥匙的拥有情况已经压缩在第三个状态里了，假设我们当前的状态是三元组\(t(x,y,key)\)，要开第\(i\)类门，则当\(t.key\) >> \(i\ \&\ 1\)为\(0\)，代表当前状态没有钥匙可以开这扇门，所以也是不能走的，\(continue\)掉\(\qquad\)\(4.\)上述条件都不满足，我们就可以快乐地扩展啦

代码

#include #include #include using namespace std;const int N = 11;int k, n, m, p, r;struct Point { int x, y, key; } ;int g[N][N][N][N], key[N][N], f[N][N][1 << N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int bfs() {    memset(f, 0x3f, sizeof f);    queue  q;    f[1][1][key[1][1]] = 0, q.push({1, 1, key[1][1]});        while (q.size())     {        auto t = q.front(); q.pop();                if (t.x == n && t.y == m) return f[t.x][t.y][t.key];                for (int i = 0; i < 4; i ++ )         {            int x = t.x + dx[i], y = t.y + dy[i];                        if (x < 1 || x > n || y < 1 || y > m) continue ;            int& door = g[t.x][t.y][x][y];            if (door == 0) continue ;            if (door >= 1 && !(t.key >> door & 1)) continue ;            int st = t.key | key[x][y];                        if (f[x][y][st] > f[t.x][t.y][t.key] + 1)             {                f[x][y][st] = f[t.x][t.y][t.key] + 1;                q.push({x, y, st});            }        }    }        return -1;}int main() {    scanf("%d%d%d", &n, &m, &p);        scanf("%d", &k);        memset(g, 0xcf, sizeof g);    while (k -- )     {        int x1, y1, x2, y2, c;        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);        g[x1][y1][x2][y2] = g[x2][y2][x1][y1] = c;    }        scanf("%d", &r);    while (r -- )     {        int x, y, q;        scanf("%d%d%d", &x, &y, &q);        key[x][y] |= 1 << q;    }        printf("%d\n", bfs());        return 0;}

这种写法是看了haaai大佬的写法后才搞明白的，\(Orz\)

\(\color{Green}{顺利Accepted!}\)

关键词：二进制位这种写法拯救大兵瑞恩