最短路首先想到bfs,但对于每个位置,拥有不同钥匙的情况下应该视为不同状态,我们在这里采用二进制进行状态压缩,同时采用哈希的思想进行判重。

#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<=c;++a)
#define MAXN 31
using namespace std;

const int dix[5] = {0,1,0,-1,0};
const int diy[5] = {0,0,1,0,-1};

struct Node {
    int x,y;
    int key;
    int step;
};

int n,m,k;
char G[MAXN][MAXN];
queue<Node> q;
unordered_map<int,bool> ha;
unordered_map<char,bool> key;

//对每个点进行hash判重
int hashNode(Node x) {
    int ret = 0;
    ret += (x.x << 15);
    ret += (x.y << 10);
    ret += x.key;

    return ret;
}

//检查是否为终局状况
bool check(Node x) {
    for(char t = 'a'; t <= 'f'; ++t)
        if(key[t])
            if(!(x.key & (1 << (t - 'a'))))
                return false;

    return true;
}

int main() {
    cin >> n >> m;

    //读图
    char ch = getchar();
    f(i,1,n) {
        f(j,1,m) {
            ch = getchar();

            G[i][j] = ch;

            if(ch == '@') {
                Node start = {i,j,0,0};
                q.push(start);
            }

            if(ch <= 'f' && ch >= 'a')
                key[ch] = true;
        }

        getchar();
    }

    while(!q.empty()) {
        Node cur = q.front();    q.pop();

        //判断是否为重复情况
        int hash = hashNode(cur);
        if(ha[hash])
            continue;
        else
            ha[hash] = true;

        //捡钥匙
        char now = G[cur.x][cur.y];
        if(now <= 'f' && now >= 'a')
            cur.key = (cur.key | (1 << (now - 'a')));

        //输出答案
        if(check(cur)) {
            cout << cur.step << endl;

            return 0;
        }

        //检查有没有钥匙,如果没有就跳过
        if(now <= 'F' && now >= 'A')
            if(!(cur.key & (1 << (now - 'A'))))
                continue;

        //这里只检查有没有墙
        f(i,1,4) {
            int nx = cur.x + dix[i],ny = cur.y + diy[i];
            if(nx > 0 && ny > 0 && nx <= n && ny <= m && G[nx][ny] != '#') {
                Node nxt = {nx,ny,cur.key,cur.step+1};
                q.push(nxt);
            }
        }
    }

    //找不到的情况
    cout << -1 << endl;

    return 0;
}
Last modification:March 5th, 2020 at 12:13 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏