智斗恶龙

题目

为了寻找能打倒恶龙的能力，MoveToEx来到了一个地宫中。
MoveToEx在刚到达地宫时，他因为传送魔法的原因，被传送到了 的位置。
由于这个地宫中特有的封印值 ，MoveToEx只能到达那些他需要走小于等于 步就能到达的格子。
在这个地宫中的某些格子中存在着一些宝藏，当MoveToEx来到这些存在宝藏的格子上时，他可以获得这些格子上的宝藏，当然他也可以选择不获取这些格子上的宝藏。每个宝藏有其特殊的能力值。
为了打败恶龙，MoveToEx至少需要 种不同能力的宝藏，但是由于MoveToEx的身体无法承受太强烈的能量差距，所以他希望他所使用的宝藏的最大与最小的能力值之差最小。
当然，地宫中有一些陷阱，MoveToEx在地宫中时不能经过这些陷阱。
求MoveToEx所使用宝藏的最大与最小的能力值之差。

给定一个 的矩阵，表示这个地宫。
用 0 表示普通的格子，用 -1 表示陷阱，其余数字表示宝藏的能力值。

解题思路

使用 BFS 算法求出能到达的格子，将这些格子中的所有宝藏的能力值记录在 中，去重，排序。

如果不同能力宝藏的个数小于 ，输出 no。

枚举拥有 种不同能力的宝藏区间，计算最大与最小能力值之差，更新最小值 。

C++代码

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
using namespace std;

int dire[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
set<long long> st;

void bfs(vector<vector<long long>>& ground, int sx, int sy, int d){
    int n = ground.size();
    int m = ground[0].size();
    if(ground[sx][sy]>0) st.insert(ground[sx][sy]);
    vector<vector<bool>> vis(n, vector<bool>(m,false));
    vis[sx][sy] = true;
    queue<pair<int,int>> que, que2, que3;
    que.push(make_pair(sx,sy));
    int level = 1;
    while(!que.empty()){
        if(level > d) return;    //超过 d 步
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for(int i=0; i<4; ++i){
            int a = x + dire[i][0];
            int b = y + dire[i][1];
            if(a>=0 && a<n && b>=0 && b<m && ground[a][b]!=-1 && vis[a][b]==false){
                if(ground[a][b]!=0)
                    st.insert(ground[a][b]);
                vis[a][b] = true;
                que2.push(make_pair(a,b));
            }
        }
        if(que.empty()){
            ++level;
            que = que2;
            que2 = que3;
        }
    }
}

int main(){
    int T;
    cin >> T;
    int n, m, sx, sy, d, x;
    while(T--){
        cin >> n >> m >> sx >> sy >> d >> x;
        --sx;
        --sy;
        vector<vector<long long>> ground(n, vector<long long>(m));
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                cin >> ground[i][j];
            }
        }
        if(ground[sx][sy]==-1){    //初始点就是陷阱
            cout << "no" << endl;
            continue;
        }
        st.clear();
        bfs(ground, sx, sy, d);
        if(st.size()<x){
            cout << "no" << endl;
        }
        else{
            if(x==1){
                cout << 0 << endl;
                continue;
            }
            vector<long long> vec(st.begin(), st.end());
            long long ans = vec.back() - vec[0];
            for(int i=x-1; i<vec.size(); ++i){
                ans = min(ans, vec[i]-vec[i-x+1]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}