题目大意：

从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数

方法一：

从s到e有两种走法。第一种是不经过d，从s到达e。第二种是先从s到k，再从k到e。bfs函数实现求出从点(x1,y1)到（x2,y2)之间的最短距离。求出s到e的距离se，s到k的距离sk，k到e的距离ke。比较se和sk+ke的大小取较小者即为答案。显然计算se，sk，ke的时候要注意se不能经过d，sk也不能经过d，只有ke可以经过d。bfs函数的参数是两个点(x1,y1)和(x2,y2)。当(x1,y1)是点s的时候不能经过d。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
int h,w;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
char g[N][N];//存图
int d[N][N];//记录bfs中每个点到起点（x1,y1)的距离
pair<int,int>S;//大写S记录s的位置，以便判断bfs函数的参数点(x1,y1)是不是s
signed bfs(pair<int,int>s,pair<int,int>e)//bfs函数的参数是两个点(x1,y1)和(x2,y2)，功能是求出这两个点之间的距离
{
    queue<pair<int,int>>q;
    memset(d,-1,sizeof d);//每次bfs前初始化d数组
    q.push(s);
    d[s.first][s.second]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if(g[x][y]!='W'&&d[x][y]==-1)//这个点不是墙并且之前没有走过这个点
            {
                if(s==S&&g[x][y]=='D') continue;//当(x1,y1)是点s的时候不能经过d。
                else
                {
                    d[x][y]=d[t.first][t.second]+1;
                    if(e==make_pair(x,y)) return d[x][y];//到达了（x2,y2)
                    q.push({x,y});
                }
            }
        }
    }
    return -1;//无法从（x1，y1）到达（x2，y2)
}
signed main()
{
    pair<int,int>s,e,di,k;//记录四个点s,e,d,k为了避免重命名将d命名为di
    cin>>h>>w;
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
        {
            cin>>g[i][j];
            if(g[i][j]=='S') S=s={i,j};
            else if(g[i][j]=='E') e={i,j};
            else if(g[i][j]=='K') k={i,j};
            else if(g[i][j]=='D') di={i,j};
        }
    int sk=bfs(s,k);
    int ke=bfs(k,e);
    int se=bfs(s,e);
    int res=1e9;
    if(se!=-1) res=se;//能从s到达e
    if(sk!=-1&&ke!=-1) res=min(res,sk+ke);//能从s到k再从k到e
    if(res==1e9) res=-1;//即无法从s到达e，又无法能从s到k再从k到e
    cout<<res;
}

方法二：

这题不同于普通的bfs，因为找到k后可以走之前走过的点。用一个结构体存每个扩展得到的点，存储点的坐标，已经走了多少步和目前是否含有钥匙。每次用t扩展点时，如果t已经有了钥匙，那么扩展得到的点也含有钥匙。如果t不含有钥匙，那么扩展得到的点也不含钥匙。找到钥匙前，走过的地方标记为D。找到钥匙后，走过的地方标记为W，这样能避免重复走，同时处理了有无钥匙的情况。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 510;
char g[N][N];//地图
int stx, sty;//s的坐标
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

struct Node//用结构体存每个点
{
    int x, y, step;//当前点的坐标，距离起点的距离
    int flag = 0; //标记当前是否已经有了钥匙;
};
queue<Node> r;

int bfs()
{
    r.push({stx,sty,0,0});//起点s入队
    g[stx][sty] = 'D';//初始没有钥匙，初始点变成D
    
    while(r.size())
    {
        auto t= r.front();
        r.pop();
        int x = t.x, y = t.y, step = t.step;

        for(int i = 0; i < 4; i++)//可以向四个方向扩展四个点
        {
            int tx = x+dir[i][0], ty = y+dir[i][1];
            
            if(g[tx][ty] == 'W') continue;//这个点是墙壁，无法通过
            else if(g[tx][ty] == 'E') return step+1;//这个点是终点
            else if(g[tx][ty] == 'K')//这个点是钥匙
            {
                g[tx][ty] = 'W';//这个点变成墙壁
                r.push({tx,ty,step+1,1});//已经有了钥匙
            }
            else if(g[tx][ty] == 'D')//这个点是门
            {
                if(!t.flag) continue;//上一个点t没有钥匙，无法通过
                r.push({tx,ty,step+1,1});//上一个点t已经有了钥匙，可以通过
                g[tx][ty] = 'W';//这个的地方变成墙壁
            }
            else if(g[tx][ty] == '.')//这个点是空地
            {
                if(t.flag)//上一个点t已经有了钥匙
                {
                    r.push({tx,ty,step+1,1});
                    g[tx][ty] = 'W';//这个的点变成墙壁
                }
                else//上一个点还没有钥匙
                {
                    r.push({tx,ty,step+1,0});
                    g[tx][ty] = 'D';//这个的点变成门
                }
            }
        }
    }
    return -1;
}

int main()
{
    int n, m; 
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin>>g[i][j];
            if(g[i][j] == 'S')
            {
                stx=i;
                sty=j;
            }
        }
    
    cout << bfs();
}