NC15136 迷宫

题目描述

这是一个关于二维迷宫的题目。我们要从迷宫的起点 '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;
}