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