比赛 20140418 评测结果 AWTTTTTTTE
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 digital-T 运行时间 7.391 s
代码语言 C++ 内存使用 1.55 MiB
提交时间 2014-04-18 09:01:37
显示代码纯文本
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int M,N,T,H[510][510];
vector <pair<int,int> > st;
class Three
{
public:
	int x,y,d;
};
class cmp
{
public:
	bool operator()(Three a,Three b)
	{
		return a.d>b.d;
	}
};
priority_queue <Three , vector<Three> , cmp> Q;
int sum;
bool walked[510][510];
void dfs(int sx,int sy,int d)
{
	sum++;
	if(sum>=T)return;
	int x,y;
	for(int i=0;i<4;i++)
	{
		x=sx+dx[i];y=sy+dy[i];
		if(x<1 || y<1 || x>M || y>N)continue;
		if(abs(H[sx][sy]-H[x][y])<=d)
		{
			dfs(x,y,d);
			if(sum>=T)return;
		}
		else
		{
			Q.push((Three){x,y,abs(H[sx][sy]-H[x][y])});
		}
	}
}
long long work(pair<int,int> p)
{
	if(T<=1)return 0;
	int D=0,x,y;
	for(int i=0;i<4;i++)
	{
		x=dx[i]+p.first;
		y=dy[i]+p.second;
		if(x<1 || y<1 || x>M || y>N)continue;
		Q.push((Three){x,y,abs(H[x][y]-H[p.first][p.second])});
	}
	memset(walked,0,sizeof(walked));
	walked[p.first][p.second]=true;
	sum=1;
	Three tmp;
	while(sum<=T)
	{
		D=Q.top().d;
		while(!Q.empty() && Q.top().d<=D)
		{
			tmp=Q.top();
			Q.pop();
			dfs(tmp.x,tmp.y,D);
		}
	}
	return (long long)D;
}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	scanf("%d%d%d",&M,&N,&T);
	for(int i=1;i<=M;i++)
	{
		for(int j=1;j<=N;j++)
		{
			scanf("%d",&H[i][j]);
		}
	}
	int tmp;
	for(int i=1;i<=M;i++)
		for(int j=1;j<=N;j++)
		{
			scanf("%d",&tmp);
			if(tmp)
				st.push_back(make_pair(i,j));
		}
	long long Ans=0;
	for(unsigned int i=0;i<st.size();i++)
		Ans+=work(st[i]);
	printf("%lld\n",Ans);
	return 0;
}