NC24569. [USACO 2014 Jan S]Cross Country Skiing
描述
输入描述
* Line 1: The integers M and N.
* Lines 2..1+M: Each of these M lines contains N integer elevations.
* Lines 2+M..1+2M: Each of these M lines contains N values that are
either 0 or 1, with 1 indicating a cell that is a waypoint.
输出描述
* Line 1: The difficulty rating for the course (the minimum value of D
such that all waypoints are still reachable from each-other).
示例1
输入:
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
说明:
If D = 21, the three waypoints are reachable from each-other. If D < 21,C++14(g++5.4) 解法, 执行用时: 292ms, 内存消耗: 18808K, 提交时间: 2020-08-25 10:16:25
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},n,m,k,s,num;
long long a[555][555],ans,maxn,sx,sy;
bool vis[555][555],v[555][555];
void dfs(int x,int y,int z){
if(x<1||y<1||x>n||y>m||vis[x][y])return ;
vis[x][y]=true;if(v[x][y])s++;
for(int i=0;i<4;i++){
int X=x+dx[i],Y=y+dy[i];
if(abs(a[x][y]-a[X][Y])<=z){
dfs(X,Y,z);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];maxn=max(maxn,a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];if(v[i][j])num++;
sx=i,sy=j;
}
}
int l=0,r=maxn+1;
while(l<=r){
int mid=(l+r)>>1;
s=0;
memset(vis,0,sizeof(vis));
dfs(sx,sy,mid);
if(s==num){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 361ms, 内存消耗: 17016K, 提交时间: 2020-04-04 16:39:27
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},n,m,k,s,num;
long long a[555][555],ans,maxn,sx,sy;
bool vis[555][555],v[555][555];
void dfs(int x,int y,int z){
if(x<1||y<1||x>n||y>m||vis[x][y])return ;
vis[x][y]=true;if(v[x][y])s++;
for(int i=0;i<4;i++){
int X=x+dx[i],Y=y+dy[i];
if(abs(a[x][y]-a[X][Y])<=z){
dfs(X,Y,z);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];maxn=max(maxn,a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];if(v[i][j])num++;
sx=i,sy=j;
}
}
int l=0,r=maxn+1;
while(l<=r){
int mid=(l+r)>>1;
s=0;
memset(vis,0,sizeof(vis));
dfs(sx,sy,mid);
if(s==num){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
return 0;
}