比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 ys 运行时间 9.001 s
代码语言 C++ 内存使用 4.79 MiB
提交时间 2014-04-18 10:12:48
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int dx[]={0,0,0,1,-1};
const int dy[]={0,1,-1,0,0};
long long n,m,t,l,r,mid,ans;
long long a[505][505];
int sx[300000],sy[300000],tot;
bool v[505][505];
struct node{
	int x,y;
};

void init(){
	int i,j,temp;
	tot=0;
	cin>>n>>m>>t;
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
		cin>>a[i][j];
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++){
		scanf("%d",&temp);
		if (temp==1) {
			sx[++tot]=i;
			sy[tot]=j;
		}
	}
}

bool judge(int x,int y,long long f){
	int i,sum=0;
	node fp,tp;
	queue<node>q;
	while (!q.empty()) q.pop();
	memset(v,0,sizeof(v));
	fp.x=x;fp.y=y;
	q.push(fp);
	sum++;
	v[x][y]=true;
	while (!q.empty()){
		fp=q.front();
		q.pop();
		for (i=1;i<=4;i++){
			tp.x=fp.x+dx[i];
			tp.y=fp.y+dy[i];
			if (tp.x>0 && tp.x<=n && tp.y>0 && tp.y<=m)
			if (abs(a[tp.x][tp.y]-a[fp.x][fp.y])<=f){
				if (!v[tp.x][tp.y]){
					q.push(tp);
					v[tp.x][tp.y]=true;
					sum++;
				}
				if (sum==t) return true;
			}
			
		}
	}
	return false;
}

void solve(){
	int i,x,y;
	ans=0;
	for (i=1;i<=tot;i++){
		x=sx[i];y=sy[i];
		l=0;r=1000000001;
		while (l<r){
			if (l==r-1){
				if (judge(x,y,l)) r=l;
				else l=r;
				break;
			}
			mid=(l+r)/2;
			if (judge(x,y,mid)) r=mid;
			else l=mid;
		}
		ans+=l;
	}
	
	cout<<ans<<endl;
}

int main(){
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
	init();
	solve();
	
	return 0;
}