「BZOJ2709」[Violet 1] 迷宫花园

2
2.5 4 5
#####
#S #
# E#
#####
21 13 12
############
#S## #E#
# ## # # #
# # # # #
### # # # #
# # # # #
# ## # # #
## # # # #
### # # # #
## # # # #
# ## # #
# # #
############

0.50000
0.21053

题解

。。。。

二分+最短路判定即可

不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#define eps 1e-7
#define p(x,y) (x-1)*m+y
#define pa pair<double,int>
#define inf 1000000000
#define ll long long 
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,x1,x2,y1,y2;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
char mp[105][105];
double L;
double mid,d[10005];
bool vis[10005];
priority_queue<pa,vector<pa>,greater<pa> >q;
void dijkstra()
{
    while(!q.empty())q.pop();
    for(int i=1;i<=n*m;i++)vis[i]=0,d[i]=1e30;
    q.push(make_pair(0,p(x1,y1)));d[p(x1,y1)]=0;
    while(!q.empty()&&!vis[p(x2,y2)])
    {
	int now=q.top().second;q.pop();
	if(vis[now])continue;vis[now]=1;
	int x=(now-1)/m+1,y=now%m;
	for(int i=0;i<4;i++)
	{
	    int nowx=x+xx[i],nowy=y+yy[i];
	    if(nowx<1||nowy<1||nowx>n||nowy>m||mp[nowx][nowy]=='#')continue;
	    double t=1;
	    if(i>=2)t=mid;
	    int to=p(nowx,nowy);
	    if(d[now]+t<d[to])	
	    {
		d[to]=d[now]+t;
		q.push(make_pair(d[to],to));
	    }
	}
    }
}
int main()
{
    int T=read();
    while(T--)
    {
	scanf("%lf",&L);n=read();m=read();char c=getchar();
	for(int i=1;i<=n;i++)
	{
	    gets(mp[i]+1);
	    for(int j=1;j<=m;j++)
	    {
	        
		if(mp[i][j]=='S')x1=i,y1=j;
		else if(mp[i][j]=='E')x2=i,y2=j;
	    }
	} 
	double l=0,r=10;
	while(l<r)
	{
	    mid=(l+r)/2.0;
	    dijkstra();
	    if(d[p(x2,y2)]<=L)l=mid+eps;
	    else r=mid-eps;
	}
	printf("%.5lf\n",l);
    }
    return 0;
}

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<vector>

#include<algorithm>

#include<map>

#define eps 1e-7

#define p(x,y) (x-1)*m+y

#define pa pair<double,int>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,x1,x2,y1,y2;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

char mp[105][105];

double L;

double mid,d[10005];

bool vis[10005];

priority_queue<pa,vector<pa>,greater<pa> >q;

void dijkstra()

{

while(!q.empty())q.pop();

for(int i=1;i<=n*m;i++)vis[i]=0,d[i]=1e30;

q.push(make_pair(0,p(x1,y1)));d[p(x1,y1)]=0;

while(!q.empty()&&!vis[p(x2,y2)])

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

int x=(now-1)/m+1,y=now%m;

for(int i=0;i<4;i++)

{

int nowx=x+xx[i],nowy=y+yy[i];

if(nowx<1||nowy<1||nowx>n||nowy>m||mp[nowx][nowy]=='#')continue;

double t=1;

if(i>=2)t=mid;

int to=p(nowx,nowy);

if(d[now]+t<d[to])

{

d[to]=d[now]+t;

q.push(make_pair(d[to],to));

}

int main()

{

int T=read();

while(T--)

{

scanf("%lf",&L);n=read();m=read();char c=getchar();

for(int i=1;i<=n;i++)

{

gets(mp[i]+1);

for(int j=1;j<=m;j++)

{

if(mp[i][j]=='S')x1=i,y1=j;

else if(mp[i][j]=='E')x2=i,y2=j;

}

double l=0,r=10;

while(l<r)

{

mid=(l+r)/2.0;

dijkstra();

if(d[p(x2,y2)]<=L)l=mid+eps;

else r=mid-eps;

}

printf("%.5lf\n",l);

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

Description

Input

Output

Sample Input

Sample Output

HINT

Source

分类目录

热门文章

Myfriends

近期评论