注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1295][SCOI2009]最长距离  

2014-10-28 15:53:42|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1295: [SCOI2009]最长距离

有水题做真开心=w=
有几个地方手残调了半天- -||

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int scan(){int i=0;scanf("%d",&i);return i;}
const int N = 30+5;
const int S[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int n,m,t;
short map[N][N],dis[N][N],v[N][N],ind[N][N];
double ans;
int calc(int x,int y){return (x-1)*(m) + y;}
queue<pair<int,int> >dui;
int main(){
//freopen("in.txt","r",stdin);
int i,j,k;
n = scan();m = scan();t = scan();
char cc;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
map[i][j] = 1;

for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
scanf(" %c",&cc);
if(cc=='1')map[i][j] = 1;
else map[i][j] = 0;
}
ans = 0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
//pre-set
int code = calc(i,j);
while(!dui.empty())dui.pop();
dui.push(pair<int,int>(i,j));
if(map[i][j])dis[i][j] = 1;
else dis[i][j] = 0;
v[i][j] = code;
ind[i][j] = 1;
//cut1
if(dis[i][j] > t)continue;
//cut2
bool ok;
if(map[i][j]==0)ok=0;
else ok = 2;
for(k=0;k<4&&ok==0;k++){
int x,y;x = i+S[k][0];y = j+S[k][1];
if(map[x][y])ok=1;
}
//spfa
if(!ok)continue;
while(!dui.empty()){
pair<int,int> now = dui.front();dui.pop();
for(k=0;k<4;k++){
int x,y;
x = now.first+S[k][0];y = now.second+S[k][1];
if(!(1<=x&&x<=n&&1<=y&&y<=m))continue;
if(v[x][y]!=code||dis[x][y] > dis[now.first][now.second] + map[x][y]){
dis[x][y] = dis[now.first][now.second] + map[x][y];
v[x][y] = code;
if(dis[x][y] > t)continue;
else ans = max(ans,hypot(fabs(x-i),fabs(y-j)));
if(!ind[x][y]){
ind[x][y] = 1;
dui.push(pair<int,int>(x,y));
}
}
}
ind[now.first][now.second]=0;
}
}
printf("%.6f\n",ans);
return 0;
}

题解:
枚举每个点作为起点,然后spfa一遍,走到一个黑格子上距离+1,在距离<=T时更新一下ans。
  评论这张
 
阅读(13)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017