C++14(g++5.4) 解法, 执行用时: 193ms, 内存消耗: 19244K, 提交时间: 2020-09-29 18:09:26

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 1005
using namespace std;
int t, n, m, i, j, k, d, c, p, x, y, z, xx, yy, zz;
long long ans, a[N][N], b[N*N], q[N*N];
int dx[]={-1, 1, 0, 0}, dy[]={0, 0, -1, 1};
void bfs(){
	p = 0;
	if(a[x][y] == -1) return;
	if(a[x][y] > 0) b[++p] = a[x][y];
	q[1] = x<<10 | y, a[x][y] = -1;
	for(i=j=1; i<=j; i++){
		x = q[i]>>10&1023, y = q[i]&1023, z = q[i]>>20;
		if(z >= d) break;
		for(k=0; k<4; k++){
			xx = x+dx[k], yy = y+dy[k], zz = z+1;
			if(xx<1 || xx>n || yy<1 || yy>m) continue;
			if(zz > d || a[xx][yy] == -1) continue;
			if(a[xx][yy] > 0) b[++p] = a[xx][yy];
			a[xx][yy] = -1;
			q[++j] = zz<<20 | xx<<10 | yy;
		}
	}
}
int main(){
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d%d%d%d", &n, &m, &x, &y, &d, &c);
		for(i=1; i<=n; i++){
			for(j=1; j<=m; j++){
				scanf("%lld", &a[i][j]);
			}
		}
		bfs();
		sort(b+1, b+p+1);
		for(n=0, i=1; i<=p; i++){
			if(b[i] != b[i-1]) b[++n] = b[i];
		}
		ans = 1e15;
		for(i=1, j=i+c-1; j<=n; i++, j++){
			if(b[j]-b[i] < ans) ans = b[j] - b[i];
		}
		if(n < c) printf("no\n");
		else printf("%lld\n", ans);
	}
	return 0;
}

C++ 解法, 执行用时: 215ms, 内存消耗: 36748K, 提交时间: 2021-05-24 20:23:26

#include<stdio.h>
#include<algorithm>
using namespace std;
long long a[1005][1005];
long long b[1000005];//记录宝藏 
int d[1005][1005];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int abs(int w1){
	if(w1>0)return w1;return -w1;
}
int p,ys,m,d1,xs,n;
void bfs(int x2,int y2){
	if(a[y2][x2]>0)b[++p]=a[y2][x2];
	int x1,y1,i;
	for(i=0;i<4;i++){
		x1=x2+dx[i];y1=y2+dy[i];
	if(a[y1][x1]!=-1&&d[y1][x1]==0&&y1>=1&&y1<=n&&x1>=1&&x1<=m&&abs(xs-x1)+abs(ys-y1)<=d1){
		d[y1][x1]=1;
		bfs(x1,y1);
	}}
}
int main()
{
	long long min;
	int i,j,x,g,t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d%d%d%d",&n,&m,&ys,&xs,&d1,&x);
		p=0;min=1e12;
		for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
		scanf("%lld",&a[i][j]);d[i][j]=0;}
		for(i=1;i<=n*m;i++)b[i]=0;
      if(a[ys][xs]==-1){
        printf("no\n");continue;
      }
		d[ys][xs]=1;
		bfs(xs,ys);
		sort(b+1,b+1+p);g=0;
		for(i=1;i+1<=p;i++){
			while(b[i]==b[i+1]){
				i++;
			}
		b[++g]=b[i];
	}
	if(b[p]!=b[p-1])b[++g]=b[p];
	for(i=x;i<=g;i++)
	if(b[i]-b[i-x+1]<min)min=b[i]-b[i-x+1];
	if(min==1e12)
	printf("no\n");
	else
	printf("%lld\n",min);
}
}

C++(g++ 7.5.0) 解法, 执行用时: 217ms, 内存消耗: 25732K, 提交时间: 2022-10-03 13:32:20

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
struct node{
	int x,y,st;
}q[1000005];
long long ans,a[1005][1005],num[1000005];
int t,n,m,i,j,sx,sy,nx,ny,d,x,l,r,tot,len;
bool ft[1005][1005];
void bfs(int x,int y){
	l=0,r=0,q[r++]=(node){x,y,0};
	node t;
	while(l<r){
		t=q[l++];
		if(t.st>=d) continue;
		for(i=0;i<4;++i){
			nx=t.x+dx[i],ny=t.y+dy[i];
			if(nx<1||nx>n||ny<1||ny>m||ft[nx][ny]||a[nx][ny]==-1) continue;
			ft[nx][ny]=1,q[r++]=(node){nx,ny,t.st+1};
			if(a[nx][ny]) num[tot++]=a[nx][ny];
		}
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		memset(a,0,sizeof(a));
		memset(ft,0,sizeof(ft));
		memset(q,0,sizeof(q));
		tot=0;
		scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&d,&x);
		for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%lld",&a[i][j]);
		if(a[sx][sy]==-1){
			printf("no\n");
			continue;
		}
		bfs(sx,sy);
		sort(num,num+tot);
		len=unique(num,num+tot)-num;
		if(len<x) printf("no\n");
		else{
			ans=1e18;
			for(i=x-1;i<len;++i) ans=min(ans,num[i]-num[i-x+1]);
			printf("%lld\n",ans);
		}
	}
	return 0;
}