题解 | #迷宫#

题目考点：bfs
题目大意：从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数
题目思路：bfs模板，找到钥匙前，走过的地方标记为D；找到钥匙后，走过的地方标记为W，这样能避免重复走，同时处理了有无钥匙的情况；
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 510;
char mp[N][N];
int stx, sty, edx, edy;

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(int n, int m)
{
    r.push({stx,sty,0,0});
    mp[stx][sty] = 'D';
    /*
      总体思路：
        找到k之前，走过的地方变成D
        找到k之后，走过的地方变成W
    */
    int flagk = 0;
    while(r.size())
    {
        auto f = r.front(); r.pop();
        int x = f.x, y = f.y, step = f.step;

        for(int i = 0; i < 4; i++)
        {
            int tx = x+dir[i][0], ty = y+dir[i][1];
            //出界直接跳过
            if(tx < 1||ty < 1||ty > m||tx > n)
                continue;
            //接下来处理各种情况
            if(mp[tx][ty] == 'W')continue;
            if(mp[tx][ty] == 'E')return step+1;
            if(mp[tx][ty] == 'K')
            {
                flagk = 1;
                mp[tx][ty] = 'W';
                r.push({tx,ty,step+1,flagk});
            }
            if(mp[tx][ty] == 'D')
            {
                if(!f.flag) continue;
                r.push({tx,ty,step+1,flagk});
                mp[tx][ty] = 'W';
            }
            if(mp[tx][ty] == '.')
            {
                if(f.flag){
                    r.push({tx,ty,step+1,1});
                    mp[tx][ty] = 'W';
                }
                else{
                    r.push({tx,ty,step+1,0});
                    mp[tx][ty] = 'D';
                }
            }
        }
    }
    return -1;
}

int main()
{
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> mp[i] + 1;

    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        if(mp[i][j] == 'S')
            stx = i, sty = j;

    cout << bfs(n,m);

    return 0;
}