题目连接

https://ac.nowcoder.com/acm/contest/7226/C

解题思路

我吐了。
思路明确:
S1:输入
S2:遍历,把能达到的点(宝藏)的值保存下来
S3:对保存下来的值进行去重操作
S4:尺取法,维护最大值与最小值的差保持最小
S5:判断输出条件并输出

有一点需要注意:
遍历统计宝藏值的时候要用bfs。
用一般的dfs是没办法访问到能到达的全部位置的,因为dfs中存在步数的特判,所以有些样例是没法遍历全部位置的,也就是没法统计全部的宝藏。
而bfs总是通过最短路径访问每个位置,所以只要是能达到的位置,一定能通过最短路径的方式访问到。
这只针对一般的dfs,通过其他方式维护一下说不定也可以,但是我不会。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1100;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll t,n,m,sx,sy,d,c,num,ans;
ll vis[M][M],mp[M][M];
ll coll[M*M];
ll cnt_dfs;
struct node{
    ll x,y,d;
};
int dir[4][2]={0,1,0,-1,1,0,-1,0};
void Input(){
    cin>>n>>m>>sx>>sy>>d>>c;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) 
            cin>>mp[i][j];
}
void bfs(){
    //特判起点 
    if(mp[sx][sy]==-1) return ;
    else if(mp[sx][sy]>0) coll[++num]=mp[sx][sy];

    queue<node> q;
    q.push((node){sx,sy,0});
    while(!q.empty()){
        node now=q.front();q.pop();
        if(now.d==d) continue;
        for(int k=0;k<4;k++){
            node tmp;
            tmp.x=now.x+dir[k][0];tmp.y=now.y+dir[k][1];
            if(tmp.x<=0||tmp.y<=0||tmp.x>n||tmp.y>m||vis[tmp.x][tmp.y]||mp[tmp.x][tmp.y]==-1) continue;    
            vis[tmp.x][tmp.y]=1;
            tmp.d=now.d+1;
            q.push(tmp);
            if(mp[tmp.x][tmp.y]>0) coll[++num]=mp[tmp.x][tmp.y];
        }
    }
} 
void solve(){
    sort(coll+1,coll+1+num);
    num=unique(coll+1,coll+num+1)-coll-1;
    for(int i=1;i<=num;i++){
        if(i+c-1>num) continue;
        ans=min(ans,coll[i+c-1]-coll[i]);
    }
}
void Init(){
    ans=INF;
    num=0;
    memset(vis,0,sizeof vis);
    memset(mp,0,sizeof mp);
    memset(coll,0,sizeof coll);
}
void test(){
    for(int i=1;i<=num;i++) cout<<coll[i]<<' ';
    cout<<endl;
}
void Output(){
    if(ans!=INF)cout<<ans<<endl;
    else cout<<"no"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        Init();
        Input();        
        bfs();
        solve();
        Output();
    }
}