http://acm.hdu.edu.cn/showproblem.php?pid=5094

给出n*m矩阵

给出k个障碍，两坐标之间存在墙或门，门最多10种，状压可搞

给出s个钥匙位置及编号，相应的钥匙开相应的门，求从1,1到n,m的最短时间，不能到底则输出-1

这里有一个大坑：有可能同一个位置有多个门或者多个钥匙...

这么坑大丈夫？

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <map>

#include <iostream>

#include <algorithm>

using namespace std;

#define RD(x) scanf("%d",&x)

#define RD2(x,y) scanf("%d%d",&x,&y)

#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

#define clr0(x) memset(x,0,sizeof(x))

#define clr1(x) memset(x,-1,sizeof(x))

#define eps 1e-9

const double pi = acos(-1.0);

typedef long long LL;

typedef unsigned long long ULL;

const int modo = 1e9 + 7;

const int INF = 0x3f3f3f3f;

const int inf = 0x3fffffff;

const LL _inf = 1e18;

const int maxn = 55,maxm = 1<<12;

int n,m,p;

bool vis[maxn][maxn][maxm];

int g[maxn][maxn][maxn][maxn],key[maxn][maxn];//0up1down2left3right

int b[12];

struct node{

    int x,y,st,t;

    node(){};

    node(int xx,int yy,int _st,int tt):x(xx),y(yy),st(_st),t(tt){};

    bool operator < (const node &a)const{

        return a.t < t;

    }

};

int dx[] = {0,0,-1,1},

    dy[] = {-1,1,0,0};

bool in(int x,int y)

{

    return 1 <= x && x<=n && 1 <= y && y <= m;

}

void bfs()

{

    priority_queue<node> q;

    q.push(node(1,1,key[1][1],0));

    vis[1][1][key[1][1]] = 1;

    while(!q.empty()){

        node cur = q.top();

        q.pop();

        if(cur.x == n && cur.y == m){

            //cout<<cur.x<<','<<cur.y<<':';

            printf("%d\n",cur.t);

            return;

        }

        int x = cur.x,y = cur.y,t = cur.t,st = cur.st;

        //cout<<x<<'.'<<y<<':'<<t<<endl;

        for(int i = 0;i < 4;++i){

            int tx = x + dx[i],ty = y + dy[i];

            if(!in(tx,ty) || g[x][y][tx][ty] & 1 == 1)continue;

            if(g[x][y][tx][ty] && !(st & g[x][y][tx][ty]))continue;

            int _st = st | key[tx][ty];

            if(!vis[tx][ty][_st]){

                vis[tx][ty][_st] = 1;

                q.push(node(tx,ty,_st,t+1));

            }

        }

    }

    puts("-1");

}

void init()

{

    for(int i = 0;i < 12;++i)

        b[i] = 1<<i;

}

void work()

{

    clr0(vis),clr0(key);

    clr0(g);

    int k,s,x,y,q,x1,y1,x2,y2,st;

    RD(k);

    while(k--){

        RD2(x1,y1),RD3(x2,y2,st);

        g[x1][y1][x2][y2] |= b[st];

        g[x2][y2][x1][y1] |= b[st];

    }

    RD(s);

    while(s--){

        RD3(x,y,q);

        key[x][y] |= b[q];

    }

    bfs();

    return ;

}

int main()

{

    init();

    while(~RD3(n,m,p)){

        work();

    }

    return 0;

}