比赛 |
20140418 |
评测结果 |
ATTTTTTTTT |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
10 |
用户昵称 |
Suke |
运行时间 |
9.001 s |
代码语言 |
C++ |
内存使用 |
3.42 MiB |
提交时间 |
2014-04-18 11:23:30 |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
bool v[502][502];
int a[502][502];
int q[250001][2];
int n,m,inf,t;
bool ok(int sx,int sy,long long de,int num){
memset(v,0,sizeof(v));
int l=1,r=1,k,x,y,ans=1,xx,yy;;
v[sx][sy]=1;
q[1][0]=sx;q[1][1]=sy;
while(l<=r){
x=q[l][0];y=q[l][1];l++;
for(k=0;k<4;++k)
{
xx=x+dx[k];yy=y+dy[k];
if (xx>0 && xx<=n && yy>0 && yy<=m)
if (!v[xx][yy])
if (abs(a[x][y]-a[xx][yy])<=de)
{
v[xx][yy]=true;
ans++;
if (ans>=num) return true;
q[++r][0]=xx;q[r][1]=yy;
}
}
}
return false;
}
long long work(int x,int y){
long long l=0,r=inf,mid;
while(l<r){
mid=(l+r)/2;
if (ok(x,y,mid,t)) r=mid;
else l=mid+1;
}
return l;
}
int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
cin>>n>>m>>t;
inf=0;
int i,j,x;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
scanf("%d",&a[i][j]);
if (a[i][j]>inf) inf=a[i][j];
}
long long ans=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j){
scanf("%d",&x);
if (x) ans+=work(i,j);
}
cout<<ans<<endl;
}