比赛 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;
}