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