题目描述

这是一个关于二维迷宫的题目。我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。
本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。
请问，从起点到终点，最少要走几步呢？

输入描述

输入的第一行有两个正整数H, W，分别代表迷宫的长跟宽。
接下来的H行代表迷宫，每行有一个长度恰为W的字串，此字串只包含'S', 'E', 'W', 'D ', 'K', '.'这几种字元。

输出描述

请在一行中输出一个整数代表答案，如果无法从起点走到终点，请输出-1。

题目分析

1. 数据存储形式
采用结构体表示图中的一个格子，包含该格子的坐标 x , y 以及从起到走到该点所需的最小步数。

struct Grid{
    int x,y,step;
    Grid(){ step = 0; }
    Grid(int a, int b, int s):x(a),y(b),step(s){}
};

2. 解题思路
从起点到终点一共存在两种可行性
1）起点直接到达终点， 起点 -> 终点。
2）通过 起点S -> 钥匙🔑 -> 门🚪 -> 终点E。
最终到达终点的可行方案
1）如果 不能直接从 起点S -> 终点E ，需要考虑 获取钥匙开门的途径，如果仍然不能到达终点，则输出 -1，否则输出到达终点的最小步数。
2）如果 起点S -> 终点E 可行 ，那么 获取钥匙开门到达终点必定可行 ，此时只需比较二者步数，获得最小步数即可。

AC代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 500 + 5;
char graph[maxn][maxn];
bool vis[maxn][maxn] = {false};
int H,W;
///上下左右
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

struct Grid{
    int x,y,step;
    Grid(){ step = 0; }
    Grid(int a, int b, int s):x(a),y(b),step(s){}
}st,ed,key,door;

int BFS(Grid src, Grid dest){
    queue<Grid> que;
    que.push(src);
    vis[src.x][src.y] = true;
    while (!que.empty()){
        Grid cur = que.front(); ///获取当前格子
        que.pop();
        ///如果当前已经到达了终点，返回行走的步数
        if (cur.x == dest.x && cur.y == dest.y){
            return cur.step;
        }
        ///如果不是，遍历四个方向
        for (int i = 0;i < 4;i ++){
            int cur_x = cur.x + dx[i];
            int cur_y = cur.y + dy[i];
            if (cur_x < 0 || cur_x >= H || cur_y < 0 || cur_y >= W ) continue; ///越界
            /// 如果该格子已访问或是墙壁和门也不能通过，后面会提到如果拿到了钥匙门随即会被赋值为 '.' 表示可以通行
            if (vis[cur_x][cur_y] || graph[cur_x][cur_y] == 'W' || graph[cur_x][cur_y] == 'D') continue;
            que.push({cur_x, cur_y, cur.step + 1});
            vis[cur_x][cur_y] = true;
        }
    }
    return -1;
}

void init(int x,int y){
    char ch = graph[x][y];
    if (ch == 'S'){
        st.x = x, st.y = y;
    } else if (ch == 'E') {
        ed.x = x, ed.y = y;
    } else if (ch == 'D') {
        door.x = x, door.y = y;
    } else {
        key.x = x, key.y = y;
    }
}

int main(){

    cin >> H >> W;
    for (int i = 0;i < H;i ++)
        for (int j = 0;j < W;j ++){
            cin >> graph[i][j] ;
            if (graph[i][j] == '.' || graph[i][j] == 'W') continue;
            init(i,j);
        }

    memset(vis,0,sizeof(vis));
    int ans = BFS(st , ed); ///可直接到达的最小步数

    memset(vis,0,sizeof(vis));
    int ans1 = BFS(st , key); ///起点到钥匙最小步数

    memset(vis,0,sizeof(vis));
    graph[door.x][door.y] = '.'; ///执行ans3时，已经拿到钥匙，可将'D'改变成'.'
    int ans2 = BFS(key , door); ///钥匙到锁最小数

    memset(vis,0,sizeof(vis));
    int ans3 = BFS(door , ed); ///锁到终点最小步数

    if(ans == -1){ ///不能直接到达终点，需要考虑使用钥匙开门
        if(ans1 == -1 || ans2 == -1 || ans3 == -1){
            cout << -1 << endl;
        } else {
            cout << ans1 + ans2 + ans3 << endl;
        }
    } else { ///可以直接到达
        cout << min(ans, ans1 + ans2 + ans3) << endl;
    }
    return 0;
}