迷宫NC15136

链接：https://ac.nowcoder.com/acm/contest/23156/1007

题目描述

这是一个关于二维迷宫的题目。我们要从迷宫的起点 'S' 走到终点 'E'，每一步我们只能选择上下左右四个方向中的一个前进一格。 'W' 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 'D' 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 'K' 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 '.' 则是代表空无一物的地方，欢迎自在的游荡。

本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。

请问，从起点到终点，最少要走几步呢？

输入描述:

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

输出描述:

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

示例1

输入

4 12

WWWWWWWWWWWW

WE.W.S..W.KW

W..D..W....W

WWWWWWWWWWWW

输出

20

示例2

输入

6 6

WWWWWW

WEWS.W

W.WK.W

W.WD.W

W.W..W

WWWWWW

输出

-1

备注:

4 ≤ H, W≤ 500

'S', 'E', 'K', 'D'各出现恰好一次

迷宫的四周(最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是 'W'

题解

先看不用钥匙能不能到达终点，若能到则将距离保存下来，再求拿到钥匙之后到达终点的距离，两者求最小值，一气呵成。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int N = 550, INF = 0x3f3f3f3f;
int h, w;
int sx, sy, ex, ey, kx, ky;
int dis[N][N];
char m[N][N];
queue<pii> q;
int fx[] = {-1, 0, 1, 0}, fy[] = {0, 1, 0, -1};

int main()
{
    cin >> h >> w;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> m[i][j];
            if(m[i][j] == 'S') sx = i, sy = j;
            if(m[i][j] == 'E') ex = i, ey = j;
            if(m[i][j] == 'K') kx = i, ky = j;
        }
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[sx][sy] = 0;
    q.push({sx, sy});
    bool key = false;
    bool flag = false;
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        if (x == ex && y == ey) {
            flag = true;
            break;  
        } 
        for (int i = 0; i < 4; i++) {
            int xx = x + fx[i], yy = y + fy[i];
            if (xx >= 1 && xx <= h && yy >= 1 && yy <= w) {
                if (m[xx][yy] == 'K' && dis[xx][yy] == INF) {
                    key = true;
                    dis[xx][yy] = dis[x][y] + 1;
                    q.push({xx, yy});
                }
                else if (m[xx][yy] != 'W' && m[xx][yy] != 'D' && dis[xx][yy] == INF) {
                    dis[xx][yy] = dis[x][y] + 1;
                    q.push({xx, yy});
                }
            }
        }
    }
    int ans = INF;
    if (flag) ans = dis[ex][ey];
    if (key) {
        int k = dis[kx][ky];
        memset(dis, 0x3f, sizeof(dis));
        dis[kx][ky] = k;
        while (q.size()) q.pop();
        q.push({kx, ky});
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            if(x == ex && y == ey) {
                break;
            }
            for (int i = 0; i < 4; i++) {
                int xx = x + fx[i], yy = y + fy[i];
                if (xx >= 1 && xx <= h && yy >= 1 && yy <= w) {
                    if (m[xx][yy] != 'W' && dis[xx][yy] == INF) {
                        dis[xx][yy] = dis[x][y] + 1;
                        q.push({xx, yy});
                    }
                }
            }
        }
        ans = min(ans, dis[ex][ey]);
    }
    if(ans == INF) cout << "-1" << endl;
    else cout << ans << endl;
    return 0;
}