题目大意

迷宫中有4个点分别是s代表起点，k代表钥匙位置，d代表门位置，e代表终点，其他地方有的是墙，有的是路，问起点到终点的最短距离。

分析

说实话，真没啥好分析的，一看就知道要分情况，而也正是分情况最难，所以我们直接放到代码里分情况讲解。

两个AC代码

两个AC代码，分的情况不同，代码2更优质。

代码1

分情况

情况1：只要绕开门走，其他地方随便走，走到出口。（因为你不能确定是否拿上钥匙了，所以干脆就不走门了）（s->e且避开d）
情况2：先去拿上钥匙，再随便走，走到出口。（已经拿上钥匙了，无论之后有没有门，你都能进去，所以想怎么走都行了）（s->k再k->e）
最后只需要将两个中小的输出就行，如果都无法到达终点，输出-1。
（说实话，你会发现两种情况有重叠的部分，比如第一种情况走到了k，且第二种情况绕开了d，重复了。因此，代码2提供了另一种分情况的方法。之所以写这个代码1的分情况的方法，是因为我发现网上的大部分题解都是这样分的，但这好像并不是最佳分法，所以我就自己又想了一种比较好的分法，在代码2中讲到。其实，读代码1的题解也有助于理解代码2，因为二者如出一辙）

代码实现

//一定要读，加快理解我写的代码，
直接扔上bfs的典型模板函数（因人而异，不同人背过的模板略有区别）
注意 ：我下面的代码1定义了三个bfs函数，bfs1，bfs2（注释掉了），bfs3。
其中bfs1用来计算情况1的最短距离，bfs2和bfs3分别用来计算情况2的s->k部分和k->e部分的最短距离。
之所以把bfs2注释掉是因为，bfs2与bfs1完全一样，而bfs3与bfs1和bfs2也只差一句话，就是bfs1的第二个continue的判断多了个“|| txm+ty==d”（提前说一下，方便大家读懂代码，要是直接让大家看，实在太难发现代码一样且太难理解）
说一下为什么：
对于情况1而言（bfs1），你不能走门，所以走到门的时候我把它continue掉，不让队列中出现门这个位置。
对于情况2而言（bfs2），在你找到钥匙之前，你是进不去门的，所以你走到门也要continue掉，因为你没钥匙无法访问门这个位置；（bfs3），bfs3没有了“|| txm+ty==d”这个判断条件，你已经有钥匙了，之后的路随便走，只要最短就行，典型的广度优先搜索找最短路径。
代码中的小技巧（雨巨都讲过）
1.你会发现，在输入的时候，我进行了s=im+j;e=im+j;等类似的操作，什么意思呢？
我是在给二维数组的每个点进行编号，每个点的标号=点所在行*二维数组的总列数+点所在列（其中二维数组的行列要从0开始），想通过标号表示点的行列坐标也很简单，点所在行=点的标号/二维数组的总列数，点所在列=点的标号%二维数组的总列数。你稍微画个二维数组的图就明白了。这样的方便之处在于，我将一个二维的数组，压缩成了一维（变相，并非真是一维），入队的就是一个数字编号而不是结构体了。
2.注意输入的时候我用的是scanf(" %c",&ch);
通过在%c前加空格可以过滤掉tab，空格，回车，我通过这个方法实现过滤行尾的回车。

AC代码

//代码1 网上分法
#include<bits/stdc++.h>
#define ll long long
#define INF 99999999
using namespace std;
const int N=550;
int n,m,k,d;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int dis[N][N],vis[N][N],mp[N][N];
int bfs1(int s,int f){//not cross door
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0||tx*m+ty==d) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];
            q.push(tx*m+ty);
        }
    }
    return INF;
}
/*
//bfs2=bfs1
int bfs2(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0||tx*m+ty==d) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];            
            q.push(tx*m+ty);
        }    
    }
    return INF;
}
*/
int bfs3(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];            
            q.push(tx*m+ty);
        }    
    }
    return INF;
}
int main(){
    int s,e;
    ll ans1,ans2,ans3;
    char ch;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            scanf(" %c",&ch);
            if(ch=='S'){s=i*m+j;mp[i][j]=1;}
            if(ch=='E'){e=i*m+j;mp[i][j]=1;}
            if(ch=='K'){k=i*m+j;mp[i][j]=1;}
            if(ch=='D'){d=i*m+j;mp[i][j]=1;}
            if(ch=='.'){mp[i][j]=1;}
            if(ch=='W'){mp[i][j]=0;}            
        }
        ans1=bfs1(s,e);
        ans2=bfs1(s,k);//等价于ans2=bfs2(s,k);
        ans3=bfs3(k,e);
        if(ans1==INF && (ans2==INF || ans3==INF))
            cout<<-1;
        else
            cout<<min(ans1,ans2+ans3);
} 

代码2

分情况

情况1：绕门而走。从起点出发到终点，绕开门走的最短距离。
情况2：入门而走。从起点出发到终点，必须走门的最短距离。
其中情况2，再细说一下。要走门，就得拿钥匙，所以我们先去拿钥匙，再奔去门，再从门到终点。（这顺序没毛病吧）
先说一下他们为什么可以分成这两种情况，其实理解很简单啊，走门和不走门两种对立情况（对立就是两种情况不能同时出现，且其中一个出现，另一种一定不出现），所以他俩就能构成本题的答案。而且不会存在重复的部分，因为对立嘛。这样就弥补了代码1的不足。

代码实现

读懂了代码1，再读代码2就太轻松了（因为我是几乎直接copy的代码1，完成的代码2的）
先讲一下这几个函数起名的规则（我自己定的，方便你理解）bfs_起点_终点(参数1：起点，参数2：终点)
bfs_s_e()用于计算情况1；bfs_s_k(),bfs_k_d(),bfs_d_e()分别用于计算s->k,k->d,d->e的最短距离。
注意：bfs_s_e()=bfs_s_k()=bfs1()=bfs2()，我都是直接copy的，肯定一样，意义一样，只是传入参数不一样导致了结果不一样。bfs_k_d()=bfs_d_e()=bfs3()，也是copy的。

AC代码

/代码2 我的分法
#include<bits/stdc++.h>
#define ll long long
#define INF 99999999
using namespace std;
const int N=550;
int n,m,k,d;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int dis[N][N],vis[N][N],mp[N][N];
//not cross door
int bfs_s_e(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0||tx*m+ty==d) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];
            q.push(tx*m+ty);
        }
    }
    return INF;
}
//cross door
int bfs_s_k(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0||tx*m+ty==d) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];
            q.push(tx*m+ty);
        }
    }
    return INF;
}
int bfs_k_d(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];
            q.push(tx*m+ty);
        }
    }
    return INF;
}
int bfs_d_e(int s,int f){
    memset(dis,0,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int tmp=q.front();
        q.pop();
        int x=tmp/m,y=tmp%m;
        vis[x][y]=1;
        for(int k=0;k<4;k++){    
            int tx=x+dir[k][0],ty=y+dir[k][1];                    
            if(tx<0||ty<0||tx>=n||ty>=m) continue;
            if(vis[tx][ty]==1||mp[tx][ty]==0) continue;
            vis[tx][ty]=1;
            dis[tx][ty]=dis[x][y]+1;
            if(tx*m+ty==f) return dis[tx][ty];
            q.push(tx*m+ty);
        }
    }
    return INF;
}
int main(){
    int s,e;
    ll ans1,ans2,ans3,ans4;
    char ch;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            scanf(" %c",&ch);
            if(ch=='S'){s=i*m+j;mp[i][j]=1;}
            if(ch=='E'){e=i*m+j;mp[i][j]=1;}
            if(ch=='K'){k=i*m+j;mp[i][j]=1;}
            if(ch=='D'){d=i*m+j;mp[i][j]=1;}
            if(ch=='.'){mp[i][j]=1;}
            if(ch=='W'){mp[i][j]=0;}            
        }
        ans1=bfs_s_e(s,e);
        ans2=bfs_s_k(s,k);
        ans3=bfs_k_d(k,d);
        ans4=bfs_d_e(d,e);
        if(ans1==INF && (ans2==INF || ans3==INF || ans4==INF))
            cout<<-1;
        else
            cout<<min(ans1,ans2+ans3+ans4);            
} 

我出现的错误（读者可略）

//第四篇公共题解
写了好久，还是只过了98%的数据。首先问题出在情况的分类没分好，并没有想到用“是否经过门”作为分界点。虽然想到了分类，但是分类的依据，如何去分类，想的不是很完美，两种情况出现了重复的部分。其次是小错误太多，之所以只过了98%的数据，好像就是因为我最后的输出结果的判断条件有点问题，导致数据停在了98%，有点可惜（debug了巨久，还是没找到）。
最后的最后我想问上天一句话：我到底什么时候才能成为大佬啊啊啊！！！