这题的思路也很妙，一个三维的最短路问题，d[x,y,state];
可以看成每走一步，d[x,y,state]->d[x,y,state|key]有一条边权为0的边
d[x,y,state]->d[a,b,state]有一条边权为1的边
终点为d[n,m,xxx],xxx可以为任何值，多终点
由于边权为0/1，可以用双端队列
为了方便，还可以把前两维映射成一维

h数组不能开小，卡了好久

#include <cstring>
#include <iostream>
#include <deque>
#include <set>

using namespace std;

const int N=11,M=N*N,P=2000;
int n,m,p,k;

int h[M],e[400],ne[400],w[400],idx;

typedef pair<int,int> pii;

int g[N][N],key[M];
//第一维为位置，第二维为钥匙状态
int dist[M][P];
int st[M][P];

set<pii> edges;

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

void build()
{
    int dx[]={-1,0,1,0};
    int dy[]={0,1,0,-1};
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int u=0;u<4;u++)
            {
                int x=i+dx[u],y=j+dy[u];
                if(!x || x>n || !y ||y>m) continue;
                int a=g[i][j],b=g[x][y];
                if(edges.count({a,b})==0)
                {
                    add(a,b,0);
                }
            }

        }
    }

}

int bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1][0]=0;
    deque<pii> q;
    q.push_back({1,0});
    while(q.size())
    {
        auto t=q.front();
        q.pop_front();
        if(st[t.first][t.second]) continue;
        st[t.first][t.second]=1;

        //cout<<dist[t.first][t.second]<<endl;

        if(t.first==n*m) return dist[t.first][t.second];

        if(key[t.first])
        {
            //<<"aaa"<<endl;
            int state=t.second|key[t.first];
            if(dist[t.first][state]>dist[t.first][t.second])
            {
                dist[t.first][state]=dist[t.first][t.second];
                q.push_front({t.first,state});
            }
        }
        for(int i=h[t.first];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(w[i] && !(t.second>>w[i]-1&1)) 
            {
                //cout<<"bb"<<endl;
                continue;

            }
            if(dist[j][t.second]>dist[t.first][t.second]+1)
            {

                dist[j][t.second]=dist[t.first][t.second]+1;
                q.push_back({j,t.second});
            }
        }
    }
    return -1;
}


int main()
{
    cin>>n>>m>>p>>k;
    for(int i=1,t=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            g[i][j]=t++;
        }
    }

    memset(h,-1,sizeof h);
    while(k--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        //二维转一维
        int a=g[x1][y1],b=g[x2][y2];
        edges.insert({a,b}),edges.insert({b,a});
        //如果c不是墙，则add边
        if(c)
        {
            add(a,b,c);
            add(b,a,c);
        }
    }
    //把剩余的没有出现过的边建上
    build();
    int s;
    cin>>s;
    while(s--)
    {
        int x,y,id;
        cin>>x>>y>>id;
        key[g[x][y]] |= 1<<id-1;
    }

    cout<<bfs();
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla