洛谷4011 孤岛营救问题

题意

有一个 $N\times M$ 的长方形迷宫，相邻两个单元之间可能有不能通过的墙或可以用第 $Q_i$ 种钥匙打开的门，有的单元中有第 $Q_i$ 种钥匙。从 $(1,1)$ 出发，目标是 $(N,M)$，每次只能移动一个单元，求最短移动时间。

其中 $N,M\le 10$ ，钥匙的种类数 $P\le 10$ 。

题解

钥匙的种类数不多，考虑直接状压搜索。

用 $s[x][y][i]$ 表示 $(x,y)$ 第 $i$ 个方向所需的钥匙，如果是墙就可以设为 $2^{11}$ 。用 $key[x][y]$ 表示 $(x,y)$ 放的钥匙种类，需要注意可能不只有一种钥匙所以要用|。

要求最短移动时间，显然 $bfs$ 。每次搜索时记录一个四元组 $(x,y,now,ans)$ ，分别代表在 $(x,y)$ ，手上的钥匙是 $now$ ，当前答案是 $ans$ 。每次枚举四个方向，如果能打开门就继续搜索，如果当前点有钥匙就把它拿上。

还有要注意循环中的下标，我因为把 $j$ 写成 $i$ 调了 $1h$ 。

#include<bits/stdc++.h>
#define T tuple<int,int,int,int>
#define TIE tie(x,y,now,ans)
#define mt make_tuple

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int s[15][15][4],key[15][15],n,m,p,k,a,b,c,d,e,x,y,now,ans;
int fx[4]={0,0,-1,1},fy[4]={-1,1,0,0};
bool vis[15][15][1024];

inline int bfs()
{
    queue <T> q;
    q.push(mt(1,1,0,key[1][1]));
    while (!q.empty())
    {
        TIE=q.front(); q.pop();
        if (x==n && y==m) return ans;
        for (int i=0;i<4;i++)
        {
            if (s[x][y][i]!=(s[x][y][i]&now)) continue;
            int tx=x+fx[i],ty=y+fy[i],nxt=now|key[tx][ty];
            if (tx<1 || tx>n || ty<1 || ty>m) continue;
            if (vis[tx][ty][nxt]) continue;
            vis[tx][ty][nxt]=1;
            q.push(mt(tx,ty,nxt,ans+1));
        }
    }
    return -1;
}

int main()
{
    n=read(); m=read(); p=read(); k=read();
    for (int i=1;i<=k;i++)
    {
        a=read(); b=read(); c=read(); d=read(); e=read();
        e=e ? e : 11;
        for (int j=0;j<4;j++)
        {
            int tx=a+fx[j],ty=b+fy[j];
            if (tx==c && ty==d)
            {
                s[a][b][j]=1<<(e-1);
                s[c][d][j^1]=1<<(e-1);
                break;
            }
        }
    }
    k=read();
    for (int i=1;i<=k;i++)
    {
        a=read(); b=read(); c=read();
        key[a][b]|=1<<(c-1);
    }
    printf("%d",bfs());
    return 0;
}