FLOW14 孤岛营救问题

模型：

分层图最短路径->最短路径

题意：

迷宫的外形是一个长方形，其南北方向被划分为 $n$ 行，东西方向被划分为 $m$ 列， 于是整个迷宫被划分为 $n×m$ 个单元。南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 $p$ 类， 打开同一类的门的钥匙相同，不同类门的钥匙不同。 大兵瑞恩被关押在 $(n,m)$ 单元里，并已经昏迷。迷宫只有一个入口， 在 $(1,1)$ 单元。麦克从一个单元移动到另一个 相邻单元的时间为 1，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。 试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

题解：

又是一道假网络流题

一道经典的状压bfs

把钥匙压成二进制，从(1,1)开始向四周bfs，对每个点的每个状态记个v数组，记录有没有走过

如果走到(n,m)就输出步数

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=12,S=1<<11;
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int loc[N][N][N][N],key[N][N],n,m,k;
bool v[N][N][S];

struct situ{
    int x,y,s,step;
};

int bfs(){
    queue<situ> q;
    q.push((situ){1,1,key[1][1],0});
    v[1][1][key[1][1]]=1;
    while(!q.empty()){
        situ now=q.front();
        q.pop();
        int x=now.x,y=now.y;
        if(x==n&&y==m) return now.step;
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||ny<1||nx>n||ny>m) continue;
            if(loc[x][y][nx][ny]==-1) continue;
            if(loc[x][y][nx][ny]!=(loc[x][y][nx][ny]&now.s)) continue;
            int ns=now.s|key[nx][ny];
            if(v[nx][ny][ns]) continue;
            v[nx][ny][ns]=1;
            q.push((situ){nx,ny,ns,now.step+1});
        }
    }
    return -1;
}

signed main(){
    read(n);read(m);read(k);read(k);
    while(k--){
        int x,y,xx,yy;
        read(x);read(y);read(xx);read(yy);
        read(loc[x][y][xx][yy]);
        if(!loc[x][y][xx][yy]) loc[x][y][xx][yy]=-1;
        else loc[x][y][xx][yy]=1<<loc[x][y][xx][yy]-1;
        loc[xx][yy][x][y]=loc[x][y][xx][yy];
    }
    read(k);
    while(k--){
        int x,y,z;
        read(x);read(y);read(z);
        key[x][y]|=1<<z-1;
    }
    write(bfs());
}