比赛 |
20140418 |
评测结果 |
AATTTTTTTE |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
20 |
用户昵称 |
LuciFer_T-J |
运行时间 |
8.241 s |
代码语言 |
C++ |
内存使用 |
2.67 MiB |
提交时间 |
2014-04-18 11:27:16 |
显示代码纯文本
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
struct node{
int x,y,w;
}heap[100005];
long long ans;
int a[505][505],n,m,pp,T;
bool v[505][505];
int abc(int x){
return x<0?-x:x;
}
void up(int x){
int i=x>>1;
if (!i) return ;
if (heap[i].w>heap[x].w){
swap(heap[i],heap[x]);
up(i);
}
}
void down(int x){
int i=x<<1;
if (i>pp) return ;
if (i<pp && heap[i].w>heap[i+1].w) i++;
if (heap[i].w<heap[x].w){
swap(heap[i],heap[x]);
down(i);
}
}
void push(node z){
heap[++pp]=z;
up(pp);
}
void del(int x){
heap[x]=heap[pp];
pp--;
down(x);
}
void bfs(int x,int y){
memset(v,0,sizeof(v));
int temp=0,now=T,i;
node z,d;
z.x=x;z.y=y;z.w=0;
pp=0;
push(z);
while (now--){
while (pp){
z=heap[1];del(1);
if (v[z.x][z.y]) continue;
v[z.x][z.y]=1;
temp=max(temp,z.w);
for (i=0;i<4;i++){
d.x=z.x+dx[i];
d.y=z.y+dy[i];
if (d.x>0 && d.x<=n && d.y>0 && d.y<=m){
d.w=abc(a[z.x][z.y]-a[d.x][d.y]);
push(d);
}
}
break;
}
}
ans+=temp;
}
int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
int i,j,ch;
scanf("%d%d%d",&n,&m,&T);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
ans=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&ch);
if (ch){
bfs(i,j);
}
}
cout<<ans<<endl;
return 0;
}