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