智斗恶龙

题目描述

MoveToEx来到了一个异次元世界,在这个世界中存在着恶龙.作为拯救世界的勇士,MoveToEx要打倒恶龙.
为了寻找能打倒恶龙的能力,MoveToEx来到了一个地宫中.MoveToEx在刚到达地宫时,他因为传送魔法的原因,被传送到了(sx,sy)的位置,而由于这个地宫中特有的封印值d,MoveToEx只能到达那些他需要走小于等于d步就能到达的格子.在这个地宫中的某些格子中存在着一些宝藏,当MoveToEx来到这些存在宝藏的格子上时,他可以获得这些格子上的宝藏,当然他也可以选择不获取这些格子上的宝藏.每个宝藏有其特殊的能力值.为了打败恶龙,MoveToEx至少需要x种不同能力的宝藏,但是由于MoveToEx的身体无法承受太强烈的能量差距,所以他希望他所使用的宝藏的最大与最小的能力值之差最小.
当然,地宫中有一些陷阱,MoveToEx在地宫中时不能经过这些陷阱.
所以请你帮助MoveToEx计算一下,MoveToEx所使用宝藏的最大与最小的能力值之差.

题目分析

1.因为题目说走到一个地方可以取它的值也可以不取，那么我们就走完所有能走的点，并记录下来，然后去重，求一个区间也就是x长度区间的最小值
2.我们需要定义一个新的数组把能走过的点的价值记录下来，然后去重，我们再遍历这个去重的区间，但是我们需要保证我们所选的区间是x长度，这就有点滑动窗口的味道了并且区间的长度不能超过去重后区间的长度。
3.然后就是变量的定义以及定义的范围，因为题目的数据很大，所以我们需要long long定义，而且在定义一个极大值的时候需要定义的足够大，比如1e17，不能定义太小了不认过不了题目

sort(ans + 1, ans + cnt + 1);//去重前一定要排序
    cnt = unique(ans + 1, ans + cnt + 1) - ans - 1;//它指向的是去重后容器中不重复序列的最后一个元素的下一个元素。
    if (cnt < len)
        return -1;
    ll inf = 1e17;//一定要定义的足够大
    for (int i = 1; i <= cnt; ++i)
    {
        ll nec = i + len - 1;//遍历整个区间的时候一定要确保nec-i的长度为len
        if (nec > cnt)//不能越界
            break;
        inf = min(inf, (ans[nec] - ans[i]));
    }
    return inf;

4.如果起点是陷阱的话那么直接结束bfs代码，直接输出no

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
typedef long long ll;

int n, m, sx, sy, d, len;
ll cnt;
ll a[maxn][maxn], vis[maxn][maxn], ans[maxn * maxn];
int dis[4][2] = {-1, 0, 1, 0, 0, 1, 0, -1};

struct node
{
    int x, y;
    node(int xx, int yy) : x(xx), y(yy) {}
};
queue<node> q;

int judge(int x, int y)
{
    if (abs(x - sx) + abs(y - sy) > d)
        return 1;
    if (x < 1 || x > n || y < 1 || y > m)
        return 1;
    return 0;
}

ll bfs(int x, int y)
{
    q.push(node(x, y));
    vis[x][y] = 1;
    if (a[x][y] == -1)
        return -1;
    while (!q.empty())
    {
        node t = q.front();
        q.pop();
        if (a[t.x][t.y] > 0)
            ans[++cnt] = a[t.x][t.y];
        for (int i = 0; i < 4; ++i)
        {
            int xx = t.x + dis[i][0];
            int yy = t.y + dis[i][1];
            if (vis[xx][yy] || a[xx][yy] == -1 || judge(xx, yy))
                continue;
            q.push(node(xx, yy));
            vis[xx][yy] = 1;
        }
    }
    sort(ans + 1, ans + cnt + 1);
    cnt = unique(ans + 1, ans + cnt + 1) - ans - 1;
    if (cnt < len)
        return -1;
    ll inf = 1e17;
    for (int i = 1; i <= cnt; ++i)
    {
        ll nec = i + len - 1;
        if (nec > cnt)
            break;
        inf = min(inf, (ans[nec] - ans[i]));
    }
    return inf;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        scanf("%d%d%d%d%d%d", &n, &m, &sx, &sy, &d, &len);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                scanf("%lld", &a[i][j]);
        ll ans = bfs(sx, sy);
        if (ans == -1)
            puts("no");
        else
            printf("%lld\n", ans);
    }
    return 0;
}