[COCI2010-2011#7] POŠTAR 题解
题目传送门
一血 搬题+翻译者填坑
题意
-
给定一个矩阵，每个点有一权值。
-
给定初始点与特殊点，可以从初始点八方向走。
-
问经过所有特殊点时，走过的最大高度减最小高度的最小值。
Sol
看到
如果暴力枚举最大值与最小值，再暴力跑图判断，则使复杂度成
显然这样过不了。/kel
Q：直接枚举答案行不行呢？
A：不行，不确定确切最大最小，无法直接跑图。
那么肯定还是要枚举一个最大值或最小值。这个选最大还是最小啊，因人而异。
我写的是最小值。
这样再加上跑图的复杂度，你就已经有
如何在
我们选择二分最大值。
最大值可能个数有
既然有了最大最小值，那么每次遍历跑图即可。
删去常数后 复杂度
可以跑过此题。（有点慢）
/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=55;
ll n,hs,h[N][N],a[N*N],vst[N][N],kx,ky,ans=0x3f3f3f3f,dx[8]={1,1,0,-1,-1,-1,0,1},dy[8]={0,-1,-1,-1,0,1,1,1};
char s[N][N];
template <typename T> void rd(T &x){
ll fl=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')fl=-fl;
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';
x*=fl;
}
void wr(ll x){
if(x<0)x=-x,putchar('-');
if(x<10)putchar(x+'0');
if(x>9)wr(x/10),putchar(x%10+'0');
}
void dfs(ll x,ll y,ll hl,ll hr){
if(vst[x][y]) return;
vst[x][y]=1;
for(ll i=0;i<8;i++){
if(x+dx[i]<0||x+dx[i]>=n||y+dy[i]<0||y+dy[i]>=n||h[x+dx[i]][y+dy[i]]<hl||h[x+dx[i]][y+dy[i]]>hr) continue;
dfs(x+dx[i],y+dy[i],hl,hr);
}
}
bool ok(ll hl,ll hr){
memset(vst,0,sizeof(vst));
if(h[kx][ky]<hl||h[kx][ky]>hr) return 0;
dfs(kx,ky,hl,hr);
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++)
if(s[i][j]=='K'&&!vst[i][j]) return 0;
return 1;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
rd(n);
for(ll i=0;i<n;i++){
scanf("%s",s[i]);
for(ll j=0;j<n;j++) if(s[i][j]=='P') kx=i,ky=j;
}
for(ll i=0;i<n;i++)
for(ll j=0;j<n;j++){rd(h[i][j]);a[hs++]=h[i][j];}
sort(a,a+hs);
hs=unique(a,a+hs)-a;
for(ll i=0;i<hs;i++){
ll l=i,r=hs-1;
while(l<=r){
ll mid=l+((r-l)>>1);
if(ok(a[i],a[mid])) r=mid-1;
else l=mid+1;
}
if(ok(a[i],a[l])) ans=min(ans,a[l]-a[i]);
}
wr(ans);puts("");
return 0;
}