自动搬运

查看原文

来自洛谷，原作者为

	EDqwq **

搬运于2025-08-24 22:05:38，当前版本为作者最后更新于2020-10-03 14:56:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道水题

思路：

看了一下数据范围，直接二分+dfs可过

二分从0到11亿左右，亲测从1开始挂掉

dfs时不要回溯，直接标记，最后用check函数判断，如果这个点是关键点，且它没有被访问过，返回$false$。如果所有的都访问过，返回$true$。

注意事项：

1. 二分记录答案当check函数返回$true$时更新为mid，不要记录为l或r。不但是这道题，二分都要这么做。

2. 判断难度值是大于等于而不是大于。

时间复杂度为$O(nm)$，绝不可能炸掉。

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
	int x;
	int y;
}e[50010];

int n,m;
int maps[1010][1010];
int ans;
int l,r,mid;
int cnt;
int sx,sy;
int fx[4][2] = {1,0,-1,0,0,1,0,-1};
bool bk[1010][1010];
bool bkk[1010][1010];

void dfs(int x,int y){
	//cout<<"x = "<<x<<" y = "<<y<<endl;
	for(int i = 0;i <= 3;i ++){
		int xx = x + fx[i][0];
		int yy = y + fx[i][1];
		//cout<<"xx = "<<xx<<" yy = "<<yy<<endl;
		if(xx >= 1 && yy >= 1 && xx <= n && yy <= m && !bk[xx][yy]){
			if(abs(maps[xx][yy] - maps[x][y]) <= mid){
				bk[xx][yy] = true;
				dfs(xx,yy);
			}
		}
	}
}

bool check(){
	memset(bk,false,sizeof(bk));
	bk[sx][sy] = true;
	dfs(sx,sy);
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			if(bkk[i][j]){
				if(!bk[i][j])return false;
			}
		}
	}
	return true;
}

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			maps[i][j] = read();
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			int xx;
			xx = read();
			if(xx == 1){
				bkk[i][j] = true;
				sx = i;
				sy = j;
			}
		}
	}
	l = 0,r = 2100000000;
	while(l <= r){
		mid = (l + r) / 2;
		if(check())r = mid - 1,ans = mid;
		else l = mid + 1;
	}
	cout<<ans;
	return 0;
}

实话说，感觉没有绿题难度。

以此纪念考场上的一道水题