AcWing1131. 拯救大兵瑞恩

标签：大兵 AcWing1131 int scanf d% 瑞恩 key y1 y2

题目传送门

解题思路

\(\qquad\)我们可以用一个状态压缩的思路，对于所有的钥匙，用来开第\(i\)类门的我们把这把钥匙放到从右往左数的第\(i\)位（这里是为了方便写，比如开第\(1\)种门的\(key[x][y] |= 1 << 1\)），这样我们在判断是否有钥匙的时候只要用到\(x\) >> \(i\) \(\& 1\)这样取二进制位下第\(i\)位的方法就行了。
\(\qquad\)钥匙处理完了，距离我们应该怎么判断呢？可以看出这其实是求从\((1,1)到(n,m)\)的最短路，而且边权是\(1\)（这里不能走的路我们都不建边），这样的路上，最短距离是可以用\(BFS\)求的

代码

#include <iostream>
#include <cstring>
#include <queue>

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 <Point> 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\)

标签：大兵,AcWing1131,int,scanf,d%,瑞恩,key,y1,y2
From： https://www.cnblogs.com/StkOvflow/p/17001793.html