带宝物的迷宫问题|BFS|C++|优先队列

输入样例

8 2
########
#S@@@@@#
#@####@#
#@####@#
#@####@#
#@####@#
#b@G@@a#
########

输出样例

19

(最优路径：S→a→G→b→G)

1. 结构体：

struct point{
    int x;
    int y;//位置
    int step=0;//S到该位置的距离
    char ch='a';//准备遇到的宝箱
    point(){}
    point(int _x,int _y,int s=0,char _ch='a'){x=_x;y=_y;step=s;ch=_ch;}
};

2.算法：BFS
优先队列顶储存step最小的point
visited[N][N]已访问列表每当遇见该遇见的宝箱，清零

【C++】STL里的priority_queue用法总结

#include
#include
using namespace std;

int N,K;

struct point{
    int x;
    int y;
    int step=0;
    char ch='a';
    point(){}
    point(int _x,int _y,int s=0,char _ch='a'){x=_x;y=_y;step=s;ch=_ch;}
};

struct cmp{
    bool operator()(point& p1,point& p2){
        return p1.step>p2.step;//注意最小堆比较>
    }
};

int main(){
    cin>>N>>K;
    string s[N];
    int visited[N][N];
    for(int i=0;i,cmp> Q;
    Q.push(begin);
    while(!Q.empty()){
        point temp=Q.top();
        Q.pop();
        int x1=temp.x;
        int y1=temp.y;
        visited[x1][y1]=1;

        if(s[x1][y1]==temp.ch){
            temp.ch=char(temp.ch+1);
            temp.step++;
            for(int i=0;i