【Poj3897】【Bzoj2709】迷宫花园

来源和评测点

Poj3897
Bzoj2709
Bzoj的在分析1,Poj的在分析2

题目

【题目大意】
普通得甚至有些二逼的矮穷挫少年——Dios,不可避免地遇到了他生命中的劫数,
白富美少女 Nyution。但是按照正常的校园故事的发展,Nyution 是无论如何不会喜欢上各方面条件都差到不行的 Dios 的。
不过,Dios 还是面对 Nyution 颤抖着说出了那三个字。Nyution既不想过分地让 Dios 伤心,又不想接受她根本看不上的 Dios,
于是决定让 Dios 走一个建在她家后院里的迷宫花园——如果 Dios 能很快地从起点走到终点,证明他的聪明才智,
Nyution就答应他的表白。
当然 Nyution 敢这么说肯定是有准备的。Nyution 的花园可以看做一个迷宫,在迷宫内部有起点和终点。
Dios 要从起点走到终点,并且他只能选择前后左右四个方向行走,而且显然不能走到篱笆上,也不能走出迷宫的边界。
Nyution 经过仔细的调查发现,Dios 移动到相邻格子的耗时肯定是 1。同时,Nyution 将在 Dios 的挑战开始前,
通过进行适当的路面调整,使 Dios 在南北方向(数据中的上下方向)的移动时间由 1 变成实数v 。
首先,Nyution不能让 Dios 过快地到达终点,这样她就得接受表白;
其次,Nyution 也不想让 Dios 开了小宇宙之后还是过慢地到达终点,这样显得她在刁难 Dios。
最后她确定了一个实数 L ——就是最坏情况(也就是 Dios 最神勇威武耗时最短的情况)下,
Dios 将花费 L 的时间由起点到达终点。但是 Nyution 显然不会求此时的v 值,于是她找到了一向以算法达人著称的你。
你当然不会拒绝白富美 Nyution 的请求,决定帮她算出此时的v 。
由于 Nyution 不仅是白富美同时也是三好学生,所以她肯定不会给你一个无解的任务。
并且,Nyution 的迷宫中一定没有水平的从起点到终点的通路。
【输入格式】
输入文件包含多个测试点。第一行包含一个整数,表示测试点的数目。
每个测试点的第一行包含实数 L 和两个整数 R ,C 。 L 的含义如上, R 表示 Nyution 的
花园南北方向的长度,C 表示花园东西方向的长度。
之后 R 行为花园的描述,每行包含C 个字符。其中空格(ASCII 码为 32)代表空地,
S 代表起点,E 代表终点,# 代表篱笆。显然,起点和终点都是空地。
对于 20% 的数据,满足1<=R,C<=10
对于另外 20% 的数据,保证答案v 的小数部分为 0
对于 100% 的数据,满足1<=R,C<=100 ,保证0<=v<10
【输出格式】
对于每组测试数据,在单独的一行内输出v 的值,保留 5 位小数。
【输入样例】
2
2.5 4 5
#####
#S #
# E#
#####
21 13 12
############
#S## #E#
# ## # # #
# # # # #
### # # # #
# # # # #
# ## # # #
## # # # #
### # # # #
## # # # #
# ## # #
# # #
############
【输出样例】
0.50000
0.21053

分析1

被卡精度的菜鸡一只
发现自己连二分都不会打了。。。
以上就是难度5的原因

然后是精品题,这是因为这道题把最短路拓展了,
希望大家和我一样,经过这个学会灵活变化,而不要太死脑筋
因为这道题可以不去建边的,一开始我还想着把所有边dfs建好,边值自己变化,
后来akc提醒才发现没必要

顺便说说,目前对稠密图的理解,通常m也就是边数至少n^2级别,这时才要用到Dijkstra

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//*******************全局常量*******************
const double eps=1e-8;
//*******************全局定义*******************
struct nod
{
int x,y;
nod() {}
nod(int xx,int yy) {x=xx,y=yy;}
};
//*******************接口*******************
double midv;
int n,m;
int stx,sty;
int edx,edy;
bool mp[110][110];
double d[110][110];
queue<nod> q;
bool b[110][110];
double spfa()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=0x3f3f3f3f,b[i][j]=0;
while(!q.empty()) q.pop();
d[stx][sty]=0;b[stx][sty]=1;q.push( nod(stx,sty) );
while(!q.empty())
{
nod tp=q.front();int xx=tp.x,yy=tp.y;
for(int i=0;i<=3;i++)
{
int tx,ty;
if(i==0) tx=xx-1,ty=yy;if(i==1) tx=xx+1,ty=yy;
if(i==2) tx=xx,ty=yy-1;if(i==3) tx=xx,ty=yy+1;
if(tx<1 or tx>n or ty<1 or ty>m or !mp[tx][ty]) continue;
double rc=(i<2)?midv:1;
if(d[tx][ty]>d[xx][yy]+rc)
{
d[tx][ty]=d[xx][yy]+rc;
if(b[tx][ty]==0)
{
b[tx][ty]=1;
q.push( nod(tx,ty) );
}
}
}
q.pop();b[xx][yy]=0;
}
return d[edx][edy];
}
//*******************主函数*******************
char s[110];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
double L;scanf("%lf%d%d",&L,&n,&m);gets(s+1);//debug
for(int i=1;i<=n;i++)
{
gets(s+1);//debug
for(int j=1;j<=m;j++)
{
if(s[j]=='#') mp[i][j]=0;
else mp[i][j]=1;
if(s[j]=='S') stx=i,sty=j;
if(s[j]=='E') edx=i,edy=j;
}
}
double l=0,r=10,ans=0;//debug -1
while(r-l>eps)//最后l==r即r-l==0
{
midv=(l+r)/2;
if(spfa()<=L+eps) ans=midv,l=midv+eps;//spfa()<=L
else r=midv-eps;
}
printf("%.5lf\n",ans);
}
}

分析2

POJ也差不多。。
已经用注释表明区别了

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//*******************全局常量*******************
const double eps=1e-8;
//*******************全局定义*******************
struct nod
{
int x,y;
nod() {}
nod(int xx,int yy) {x=xx,y=yy;}
};
//*******************接口*******************
double midv;
int n,m;
int stx,sty;
int edx,edy;
bool mp[110][110];
double d[110][110];
queue<nod> q;
bool b[110][110];
double spfa()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=0x3f3f3f3f,b[i][j]=0;
while(!q.empty()) q.pop();
d[stx][sty]=0;b[stx][sty]=1;q.push( nod(stx,sty) );
while(!q.empty())
{
nod tp=q.front();int xx=tp.x,yy=tp.y;
for(int i=0;i<=3;i++)
{
int tx,ty;
if(i==0) tx=xx-1,ty=yy;if(i==1) tx=xx+1,ty=yy;
if(i==2) tx=xx,ty=yy-1;if(i==3) tx=xx,ty=yy+1;
if(tx<1 or tx>n or ty<1 or ty>m or !mp[tx][ty]) continue;
double rc=(i<2)?midv:1;
if(d[tx][ty]>d[xx][yy]+rc)
{
d[tx][ty]=d[xx][yy]+rc;
if(b[tx][ty]==0)
{
b[tx][ty]=1;
q.push( nod(tx,ty) );
}
}
}
q.pop();b[xx][yy]=0;
}
return d[edx][edy];
}
//*******************主函数*******************
char s[110];
int main()
{
int T;scanf("%d",&T);
for(int tt=1;tt<=T;tt++)
{
double L;
//scanf("%lf%d%d",&L,&n,&m);
scanf("%lf%d",&L,&n);
gets(s+1);//debug
for(int i=1;i<=n;i++)
{
gets(s+1);//debug
m=strlen(s+1);
for(int j=1;j<=m;j++)
{
if(s[j]=='#') mp[i][j]=0;
else mp[i][j]=1;
if(s[j]=='S') stx=i,sty=j;
if(s[j]=='E') edx=i,edy=j;
}
}
double l=0,r=10,ans=0;//debug -1
while(r-l>eps)//最后l==r即r-l==0
{
midv=(l+r)/2.0;
if(spfa()<=L+eps) ans=midv,l=midv+eps;//spfa()<=L
else r=midv-eps;
}
printf("Case #%d: %.3lf%%\n",tt,ans*100.0);
//printf("%.5lf\n",ans);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-02/迷宫花园.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%