loj 6121「网络流 24 题」孤岛营救问题

题目链接:https://loj.ac/problem/6121

题意:略。

思路:BFS+状态压缩。去掉钥匙这个条件,这个题目就是很常见的迷宫问题,但这里由于这里多了钥匙,所以我们要添加状态来记录,但是钥匙有10把,多开10维感觉内存要爆炸,所以我们这里用状态压缩,就是用二进制来表示每个钥匙的状态1表示已经拿到0表示没有拿到,10把钥匙,假设拿到了第一把钥匙那么状态就是00000000010,所以状态数就被压缩到了1<<11,所以我们开三维vis数组来记录状态然后BFS一下即可。对于这个墙,我们开4维数组maze[a][b][c][d]来记录(a,b)到(c,d)的墙或者说门的种类即可,要学会用。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
using namespace std;
typedef long long ll;
const int maxn=10+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Node{
    int x,y;
    int step;
    int key;
};
int maze[maxn][maxn][maxn][maxn];
int kk[maxn][maxn];
bool vis[maxn][maxn][1<<11];
int n,m,p,k,s;
int dir_x[4]={0,1,0,-1};
int dir_y[4]={1,0,-1,0};
bool judge(int a,int b,int c,int d,int key){
    int x=maze[a][b][c][d];
    if (x==-1) return true;
    else if (x==0) return false;
    else{
        int t=key&(1<<x);
        if (t!=0) return true;
        else return false;
    }
}
int main(){
    read(n),read(m),read(p);
    read(k);
    memset(maze,-1,sizeof(maze));
    for (int i=1;i<=k;i++){
        int x1,y1,x2,y2,g;
        read(x1),read(y1),read(x2),read(y2),read(g);
        maze[x1][y1][x2][y2]=maze[x2][y2][x1][y1]=g;
    }
    read(s);
    for (int i=1;i<=s;i++){
        int a,b,c;
        read(a),read(b),read(c);
        kk[a][b]|=1<<c;
    }
    bool flag=false;
    Node cur,nxt;
    queue<Node>Q;
    cur.x=1,cur.y=1,cur.step=0,cur.key=0;
    vis[1][1][0]=true;
    Q.push(cur);
    while (!Q.empty()){
        cur=Q.front();Q.pop();
        if (cur.x==n && cur.y==m){
            flag=true;
            printf("%d\n",cur.step);
            break;
        }
        for (int i=0;i<4;i++){
            int tx=cur.x+dir_x[i];
            int ty=cur.y+dir_y[i];
            if (tx<1 || tx>n || ty<1 || ty>m || !judge(cur.x,cur.y,tx,ty,cur.key)) continue;
            nxt.key=cur.key|kk[tx][ty];
            if (vis[tx][ty][nxt.key]) continue;
            nxt.x=tx,nxt.y=ty,nxt.step=cur.step+1;
            vis[tx][ty][nxt.key]=true;
            Q.push(nxt);
        }
    }
    if (!flag) puts("-1");
    return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注