比赛 |
20140418 |
评测结果 |
ATTTTTTTTT |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
10 |
用户昵称 |
ys |
运行时间 |
9.001 s |
代码语言 |
C++ |
内存使用 |
4.79 MiB |
提交时间 |
2014-04-18 10:12:48 |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
long long n,m,t,l,r,mid,ans;
long long a[505][505];
int sx[300000],sy[300000],tot;
bool v[505][505];
struct node{
int x,y;
};
void init(){
int i,j,temp;
tot=0;
cin>>n>>m>>t;
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++){
scanf("%d",&temp);
if (temp==1) {
sx[++tot]=i;
sy[tot]=j;
}
}
}
bool judge(int x,int y,long long f){
int i,sum=0;
node fp,tp;
queue<node>q;
while (!q.empty()) q.pop();
memset(v,0,sizeof(v));
fp.x=x;fp.y=y;
q.push(fp);
sum++;
v[x][y]=true;
while (!q.empty()){
fp=q.front();
q.pop();
for (i=1;i<=4;i++){
tp.x=fp.x+dx[i];
tp.y=fp.y+dy[i];
if (tp.x>0 && tp.x<=n && tp.y>0 && tp.y<=m)
if (abs(a[tp.x][tp.y]-a[fp.x][fp.y])<=f){
if (!v[tp.x][tp.y]){
q.push(tp);
v[tp.x][tp.y]=true;
sum++;
}
if (sum==t) return true;
}
}
}
return false;
}
void solve(){
int i,x,y;
ans=0;
for (i=1;i<=tot;i++){
x=sx[i];y=sy[i];
l=0;r=1000000001;
while (l<r){
if (l==r-1){
if (judge(x,y,l)) r=l;
else l=r;
break;
}
mid=(l+r)/2;
if (judge(x,y,mid)) r=mid;
else l=mid;
}
ans+=l;
}
cout<<ans<<endl;
}
int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
init();
solve();
return 0;
}