比赛 20140418 评测结果 AATTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 20
用户昵称 King 运行时间 8.949 s
代码语言 C++ 内存使用 15.55 MiB
提交时间 2014-04-18 09:21:35
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 1000
struct point
{
	int x,y;
}q[MAXN*MAXN];
ll ans;
int n,m,t,h[MAXN][MAXN],ermax,ti[MAXN][MAXN],tinow;
int check(int lim,int x,int y)
{
	tinow++;int cnt=0,ql=1,qr=1;
	ti[x][y]=tinow;cnt++;q[1].x=x;q[1].y=y;
	while(ql<=qr)
	{
		point k=q[ql];
		if(k.x>1 && ti[k.x-1][k.y]!=tinow && abs(h[k.x][k.y]-h[k.x-1][k.y])<=lim){q[++qr].x=k.x-1;q[qr].y=k.y;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
		if(k.x<n && ti[k.x+1][k.y]!=tinow && abs(h[k.x][k.y]-h[k.x+1][k.y])<=lim){q[++qr].x=k.x+1;q[qr].y=k.y;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
		if(k.y>1 && ti[k.x][k.y-1]!=tinow && abs(h[k.x][k.y]-h[k.x][k.y-1])<=lim){q[++qr].x=k.x;q[qr].y=k.y-1;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
		if(k.y<m && ti[k.x][k.y+1]!=tinow && abs(h[k.x][k.y]-h[k.x][k.y+1])<=lim){q[++qr].x=k.x;q[qr].y=k.y+1;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
		ql++;
	}
	return cnt;
}
void work(int x,int y)
{
	int el=0,er=ermax,re;
	while(el<=er)
	{
		int mid=el+er>>1;
		if(check(mid,x,y)>=t){re=mid;er=mid-1;}
		else el=mid+1;
	}
	ans+=ll(re);
}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&h[i][j]),ermax=ermax>h[i][j]?ermax:h[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int ha;
			scanf("%d",&ha);
			if(ha)work(i,j);
		}
	printf("%lld\n",ans);
	return 0;
}