比赛 |
20140418 |
评测结果 |
ATTTTTTTTT |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
10 |
用户昵称 |
FF_Sky||幻 |
运行时间 |
9.001 s |
代码语言 |
C++ |
内存使用 |
20.70 MiB |
提交时间 |
2014-04-18 10:57:11 |
显示代码纯文本
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const int tx[4] = {-1,0,0,1};
const int ty[4] = {0,-1,1,0};
struct arr{
int x,y;
}q[2000000],st[250000];
int n,m,T,d[510][510],a[510][510],num,s[510][510];
bool v[510][510];
long long ans;
bool bfs(int i,int temp){
memset(v,0,sizeof(v));
int l = 1,r = 1,x,y,j,xx,yy,sum = 1;
q[l] = st[i];
v[st[i].x][st[i].y] = 1;
while (l <= r){
x = q[l].x; y = q[l].y;
l++;
for (j = 0; j < 4; j++){
xx = x+tx[j]; yy = y+ty[j];
if (xx > 0 && xx <= n && yy > 0 && yy <= m &&abs(a[xx][yy]-a[x][y]) <= temp && !v[xx][yy]){
v[xx][yy] = 1;
q[++r].x = xx; q[r].y = yy;
sum++;
if (sum == T) return 1;
}
}
}
return 0;
}
int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
int temp,i,j,k,x,y;
scanf("%d%d%d",&n,&m,&T);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++){
scanf("%d",&a[i][j]);
}
int ll = INF,rr = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
for (k = 0; k < 4; k++){
x = i+tx[k]; y = j+ty[k];
if (x > 0 && x <= n && y > 0 && y <= m){
ll = min(ll,abs(a[x][y]-a[i][j]));
rr = max(rr,abs(a[x][y]-a[i][j]));
}
}
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++){
scanf("%d",&x);
if (x == 1){
st[++num].x = i;
st[num].y = j;
}
}
int l,r;
for (i = 1; i <= num; i++){
l = ll; r = rr;
while (l < r){
int mid = (l+r)>>1;
if (bfs(i,mid)) r = mid;
else l = mid+1;
}
ans += l;
}
printf("%lld",ans);
return 0;
}