bzoj1295 最长距离
2024-09-06 13:03:30
Description
windy有一块矩形土地,被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从X走到Y。 如果windy可以移走T块障碍物,求所有格子间的最大距离。 保证移走T块障碍物以后,至少有一个格子不含有障碍物。
Input
输入文件maxlength.in第一行包含三个整数,N M T。 接下来有N行,每行一个长度为M的字符串,'0'表示空格子,'1'表示该格子含有障碍物。
Output
输出文件maxlength.out包含一个浮点数,保留6位小数。
Sample Input
【输入样例一】
3 3 0
001
001
110
3 3 0
001
001
110
【输入样例二】
4 3 0
001
001
011
000
【输入样例三】
3 3 1
001
001
001
Sample Output
【输出样例一】
1.414214
【输出样例二】
3.605551
【输出样例三】
2.828427
1.414214
【输出样例二】
3.605551
【输出样例三】
2.828427
一道spfa,打码20分钟,debug两小时,总是wa一组数据,让妹子帮忙debug,然后2个小时过去了。。最后发现是写spfa的循环队列的时候,mod应该是maxnn写成了maxn,太对不起妹子啦。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=30+5,maxnn=maxn*maxn;
int n,m,T;
bool tu[maxnn];
double ans; int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
} int fir[maxnn],nxt[4*maxnn],to[4*maxnn],e=0;
void add(int x,int y) {
to[++e]=y;nxt[e]=fir[x];fir[x]=e;
to[++e]=x;nxt[e]=fir[y];fir[y]=e;
} double get_dis(int x,int y) {
int a1=(x-1)/m+1,b1=(x-1)%m+1;
int a2=(y-1)/m+1,b2=(y-1)%m+1;
double c1=(double)a2-(double)a1,c2=(double)b2-(double)b1;
return sqrt(c1*c1+c2*c2);
} int dis[maxnn],zz[maxnn];
bool vis[maxnn];
void spfa(int st,bool p) {
int s=1,t=0,x,y,z;
memset(vis,0,sizeof(vis));
memset(dis,0x3f3f3f3f,sizeof(dis));
vis[st]=1;zz[++t]=st;dis[st]=p;
while(s<=t) {
x=zz[s%maxnn];//
for(y=fir[x];y;y=nxt[y]) {
z=to[y];
if(dis[x]+tu[z]>T||dis[x]+tu[z]>=dis[z]) continue;
dis[z]=dis[x]+tu[z];
if(!vis[z]) {
vis[z]=1;t++;
zz[t%maxnn]=z;//
}
}
s++;vis[x]=0;
}
for(int i=1;i<=n*m;++i) if(dis[i]<=T) {
double ff=get_dis(i,st);
if(ff>ans)
ans=max(ans,ff);
}
} int main() {
n=read();m=read();T=read(); int x,z;char y;
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
y=getchar();
while(y<'0'||y>'1') y=getchar();
x=(i-1)*m+j;
z=tu[x]=y-'0';
if(i>1) add(x,x-m);
if(j>1) add(x,x-1);
}
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) {
x=(i-1)*m+j;spfa(x,tu[x]);
}
printf("%.6lf",ans);
return 0;
}
最新文章
- .NET Core 1.0.1 升级汇总
- homework 11 2016 5 13 读入文件做输入
- .NET Core 和 ASP.NET 5 RC1 发布
- C# ASP.NET基类,常用类库及源代码
- 学习总结 java基础
- Spark Tungsten揭秘 Day2 Tungsten-sort Based Shuffle
- 聊聊LAA(LARGE ADDRESS AWARE)
- Linux shell日常命令和技巧
- Word Ladder 解答
- oracle中 some、any、all 三者的区别及个人总结,归纳!
- 10min系列之二日志可视化进阶
- 自己写的一个简单的Tab类
- 浅析CDN存在的必要性
- 同步、异步、阻塞、非阻塞IO
- Java之路——名词解释(一)
- 新注册第一帖----------------------乱码新手自学.net 之Linq 入门篇
- Oracle SQL 语言分类
- netty源码分析
- nyoj44 子串和 线性DP
- HighCharts之2D数值带有百分数的面积图
热门文章
- MYSQL数据库练习题操作(select)大全
- 桥接模式(Bridge、Implementor)(具体不同平台日志记录,抽象与实现分离)
- python利用paramiko执行服务器命令
- hibernate hql语句 group by having 的坑
- 文本流向 layout-flow
- mysql连接出现Unknown system variable &#39;tx_isolation&#39;异常
- expect.js
- input只能输入数字和小数点,并且只能保留小数点后两位 - CSDN博客
- 小米网关api
- leetcode 21-30 easy