比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 ◆半城烟沙灬為你打天下 运行时间 9.013 s
代码语言 C++ 内存使用 3.90 MiB
提交时间 2014-04-18 11:19:55
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int map[600][600],q[200005][2];
bool v[600][600],vv[600][600];
int n,m,ans,head,tail,ed;
int dx[5],dy[5];
bool spfa(int w,int x,int y)
{
	int xx,yy,x1,y1;
	head=tail=1;
	memset(vv,1,sizeof(vv));
	q[1][1]=x;
	q[1][2]=y;
	vv[x][y]=false;
	while (head<=tail)
	{
		xx=q[head][1];
		yy=q[head][2];
		for (int i=1;i<=4;i++)
		{
			x1=xx+dx[i];
			y1=yy+dy[i];
			if (x1>0&&y1>0&&x1<=n&&y1<=m&&vv[x1][y1])
			{
				if (abs(map[xx][yy]-map[x1][y1])<=w)
				{
					tail++;
					if (tail==ed) return true;
					q[tail][1]=x1;
					q[tail][2]=y1;
					vv[x1][y1]=false;
				}
			}
		}
		head++;
	}
	return false;
}
int find(int l,int r,int x,int y)
{
	while (l<r-1)
	{
		int mid=(l+r)/2;
		if (spfa(mid,x,y)) r=mid;
		else l=mid+1;
	}
	if (spfa(l,x,y)) return l;
	else return r;
}
int main()
{
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	dx[1]=0;dx[2]=0;dx[3]=1;dx[4]=-1;
	dy[1]=-1;dy[2]=1;dy[3]=0;dy[4]=0;
	scanf("%d%d%d",&n,&m,&ed);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	memset(v,0,sizeof(v));
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			int x;
			scanf("%d",&x);
			if (x==1) v[i][j]=true;
		}
	}
	int ans=0;
	int INF=100000000;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			if (v[i][j])
			{
				int temp=find(0,INF,i,j);
				ans+=temp;
			}
	}
	printf("%d",ans);
}