codevs 1911孤島營救問題/2219拯救大兵瑞恩

題目描述 Description

1944 年，特種兵麥克接到國防部的指令，要求立即趕赴太平洋上的一個孤島，營救被

敵軍俘虜的大兵瑞恩。瑞恩被關押在一個迷宮裡，迷宮地形複雜，但幸好麥克得到了迷宮的

地形圖。迷宮的外形是一個長方形，其南北方向被劃分為N 行，東西方向被劃分為M列，

于是整個迷宮被劃分為N×M 個單元。每一個單元的位置可用一個有序數對(單元的行号，

單元的列号)來表示。南北或東西方向相鄰的2 個單元之間可能互通，也可能有一扇鎖着的

門，或者是一堵不可逾越的牆。迷宮中有一些單元存放着鑰匙，并且所有的門被分成P類，

打開同一類的門的鑰匙相同，不同類門的鑰匙不同。

大兵瑞恩被關押在迷宮的東南角，即(N，M)單元裡，并已經昏迷。迷宮隻有一個入口，

在西北角。也就是說，麥克可以直接進入(1，1)單元。另外，麥克從一個單元移動到另一個

相鄰單元的時間為1，拿取所在單元的鑰匙的時間以及用鑰匙開門的時間可忽略不計。

«程式設計任務：

試設計一個算法，幫助麥克以最快的方式到達瑞恩所在單元，營救大兵瑞恩。

輸入描述 Input Description

第1行有3個整數，分别表示N,M,P的值。第2 行是1

個整數K，表示迷宮中門和牆的總數。第I+2 行（1<=I<=K），有5 個整數，依次為

Xi1,Yi1,Xi2,Yi2,Gi：

當Gi>=1時，表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一扇第Gi類的門，當Gi=0 時，

表示(Xi1,Yi1)單元與(Xi2,Yi2)單元之間有一堵不可逾越的牆（其中，|Xi1-Xi2|+|Yi1-Yi2|=1，

0<=Gi<=P）。

第K+3行是一個整數S，表示迷宮中存放的鑰匙總數。

第K+3+J 行(1<=J<=S)，有3個整數，依次為Xi1,Yi1,Qi：表示第J 把鑰匙存放在(Xi1,Yi1)

單元裡，并且第J 把鑰匙是用來開啟第Qi類門的。（其中1<=Qi<=P）。

輸入資料中同一行各相鄰整數之間用一個空格分隔。

輸出描述 Output Description

将麥克營救到大兵瑞恩的最短時間的值輸出。如果問題無解，則輸出-1。

樣例輸入 Sample Input

4 4 9

9

1 2 1 3 2

1 2 2 2 0

2 1 2 2 0

2 1 3 1 0

2 3 3 3 0

2 4 3 4 1

3 2 3 3 0

3 3 4 3 0

4 3 4 4 0

2

2 1 2

4 2 1

樣例輸出 Sample Output

14

其實這道題先前做kac的迷宮的時候接觸過，但這道題稍難一些

題目大意是要在地圖上有一些單元之間兩兩有牆，如果有相應的鑰匙就可以開門（牆），但有些牆是開不了的，即使有鑰匙也不行QAQ

這樣的話就可以使用bfs來解決這道題

在搜尋過程中儲存坐标和已擁有的鑰匙數

類似分層的思想，擁有不同的鑰匙進行不同的bfs操作

如果可以到達終點的話即是最終答案

儲存鑰匙時可以使用壓位操作，這樣隻需要3維數組就可以維護狀态（某神犇開12維數組用血淋淋的教訓告訴我們還是壓位好用）

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int map[][];
int door[][][][];
bool use[][][];
int x_x[]={,,,,-};
int y_y[]={,,-,,};
struct doubi{
    int x,y,k;
    int g;
};
int n,m,p,k;
queue<doubi> q;
bool can(int x,int y)
{
    if(x>=&&x<=n&&y>=&&y<=m){
        return true;
    }
    return false;
}
bool havekey(int k,int num)
{
    return k&(<<num);
}
void addkey(int &k,int num)
{
    k|=num;
    return ;
}
bool flag=;
void bfs()
{
    doubi fuckcy;
    fuckcy.x=,fuckcy.y=;
    fuckcy.k=,fuckcy.g=;
    use[][][]=;
    q.push(fuckcy);
    while(!q.empty()){
        doubi facy=q.front();
        q.pop();
        int x=facy.x,y=facy.y;
        if(x==n&&y==m){
            cout<<facy.g<<endl;
            flag=;
            return;
        }
        for(int i=;i<=;i++){
            int X=x+x_x[i];
            int Y=y+y_y[i];
            doubi nxt=facy;
            nxt.x=X,nxt.y=Y;
            if(can(X,Y)&&!use[X][Y][facy.k]){
                if(door[x][y][X][Y]==) continue;
                if(door[x][y][X][Y]){
                    if(havekey(nxt.k,door[x][y][X][Y])){
                        nxt.g=facy.g+;
                        if(map[X][Y])
                        addkey(nxt.k,map[X][Y]);
                        use[X][Y][nxt.k]=;
                        q.push(nxt);
                    }
                    else continue;
                }
                else{
                    nxt.g=facy.g+;
                    if(map[X][Y])
                    addkey(nxt.k,map[X][Y]);
                    use[X][Y][nxt.k]=;
                    q.push(nxt);
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m>>p;
    cin>>k;
    for(int i=;i<=k;i++){
        int x1,y1,x2,y2,v;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
        if(v==){
            v=;
        }
        door[x1][y1][x2][y2]=v;
        door[x2][y2][x1][y1]=v;
    }
    int s;
    cin>>s;
    for(int i=;i<=s;i++){
        int x,y,q;
        scanf("%d%d%d",&x,&y,&q);
        map[x][y]|=<<q;
    }
    bfs();
    if(!flag){
        cout<<"-1"<<endl;
    }
    return ;
}
           

順帶一提codevs拯救大兵瑞恩其中一個點的資料是錯的

要想過的話還是打個表比較好= =