这是为什么呢???(玄二关)
  • 板块灌水区
  • 楼主luogu_fkx
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/11/6 19:04
  • 上次更新2024/11/6 21:05:36
查看原帖
这是为什么呢???(玄二关)
1229527
luogu_fkx楼主2024/11/6 19:04

题目描述 奶牛们的全国冬季滑雪运动会的场地是一个M*N的矩阵。矩阵中的每个小方格上的数代表的是每块地方的高度,范围是0到1000000000之间的整数。

矩阵中某些小方格被认为是中转点,主办方希望能够设置一个最小的D值,使得每只奶牛从任意一个中转点出发都可以到达其他任意的中转点。每次行走都是向相邻的小方格移动的,相邻的小方格指得是上下左右直接相接的小方格。如果相邻的小方格之间的高度差的绝对值小于等于D,则奶牛可以在两个相邻的小方格之间移动。

请计算这个最小的D值,使得奶牛能够从任意一个中转点出发通过移动到达其他任意中转点。 输入 第一行是两个正整数M和N。 第二行到到M+1行,每行N个整数,表示每个小方格的高度。 第M+2行到第2M+1行,每行N个整数,要么是0,要么是1,1表示该位置所对应的小方格是中转点,0表示该位置所对应的小方格不是中转点。

输出 输出最小的D值。
样例输入

3 5 20 21 18 99 5 19 22 20 16 26 18 17 40 60 80 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1

样例输出

21

提示 数据范围:1<=M,N<=500,每个小方格的高度范围是0到1000000000之间的整数。 样例说明:样例中,如果D=21,则中转点之间是相互可达的,如果D<21,则右上角的中转点就不能到达其他的中转点了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int e[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,i,j,a[510][510],d[510][510],x,y,t,w,bao,mid,b[250010],c[250010],f[510][510];
bool pd(int xx){
	int t=w=1,fx,fy,i,sx,sy,j;
	memset(f,0,sizeof(f));
	b[1]=x;c[1]=y;f[x][y]=1;
	while(t<=w){
		fx=b[t];fy=c[t];
		for(i=0;i<4;i++){
			sx=fx+e[i][0];sy=fy+e[i][1];
			if(sx<1||sy<1||sx>n||sy>m)continue;
			if(f[sx][sy])continue;
			if(abs(a[sx][sy]-a[fx][fy])<=xx)
				b[++w]=sx,c[w]=sy,f[sx][sy]=1;
		}
		t++;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(d[i][j]&&!f[i][j])
				return 0;
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			cin>>a[i][j];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			cin>>d[i][j];
			if(d[i][j]==1)x=i,y=j;
		}
	t=0;w=1e9;bao=1e9;
	while(t<=w){
		mid=(t+w)/2;
		if(pd(mid))bao=mid,w=mid-1;
		else t=mid+1;
	}
	cout<<bao;
	return 0;
}



而我却输出28

2024/11/6 19:04
加载中...