题目描述

Description

Input

Output

Sample Input

5
10.28 9 9
#########
#       #
# # # # #
#S#     #
##### # #
##  #   #
# ### ###
##E     #
#########
4.67 9 9
#########
#  ##  ##
### #S# #
#  # E ##
# # #####
# ##  ###
# ##### #
#    #  #
#########
39.06 9 9
#########
#       #
# # # # #
# E# #  #
# # # # #
## ###  #
# # #S# #
#####   #
#########
24.00 9 9
#########
#      ##
# # ## ##
#   #  ##
###S## E#
### #  ##
# #   # #
##### # #
#########
25.28 9 9
#########
# S##E# #
# ### # #
# ##    #
# ##  ###
# #  ####
# # # ###
#       #
#########

Sample Output

0.41000
4.67000
3.34000
5.00000
1.69000

HINT

题目分析

二分+堆优化dij判定
这个dij有点像bfs

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int T,n,m,px,py,lx,ly;
char s[110],sa[110][110];
bool vis[50005];
double dis[50005],L;
int d(int x,int y) { return (x-1)*m+y; }
int dx[]={-1,1,0,0},dy[]={0,0,1,-1};
struct your
{
    double c;
    int x,y;
};
struct cmp
{
    bool operator() (const your j,your k)
    {
        return j.c>k.c;
    }
};
void dij(double mid)
{
    priority_queue<your,vector<your>,cmp> q;
    memset(vis,0,sizeof vis); 
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) dis[d(i,j)]=1e30;
    dis[d(px,py)]=0;
    your tmp;
    tmp.x=px,tmp.y=py,tmp.c=0;
    q.push(tmp);
    while(q.size())
    {
        your x=q.top();
        q.pop();
        if(vis[d(x.x,x.y)]) continue;
        vis[d(x.x,x.y)]=1;
        if(d(x.x,x.y)==d(lx,ly)) return ; 
        for(int i=0;i<4;i++)
        {
            int dxx=dx[i]+x.x,dyy=dy[i]+x.y;
            if(dxx<1||dxx>n||dyy<1||dyy>m||sa[dxx][dyy]=='#') continue;
            double t=1;
            if(i==0||i==1) t=mid;
            if(dis[d(dxx,dyy)]>dis[d(x.x,x.y)]+t)
            {
                dis[d(dxx,dyy)]=dis[d(x.x,x.y)]+t;
                tmp.x=dxx,tmp.y=dyy,tmp.c=dis[d(x.x,x.y)]+t;
                q.push(tmp);
            }
        }
    }
}
int main()
{   
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%d%d\n",&L,&n,&m);
        for(int i=1;i<=n;i++)
        {
            gets(sa[i]+1);
            for(int j=1;j<=m;j++)
            { 
                if(sa[i][j]=='S') px=i,py=j;
                else if(sa[i][j]=='E') lx=i,ly=j;
            }
        }
        double l=0.00,r=10,mid,ans=0.00;
        while(r-l>1e-7)
        {
            mid=(l+r)/2,dij(mid);
            if(dis[d(lx,ly)]<=L) l=mid,ans=mid;
            else r=mid;
        }
        printf("%.5lf\n",ans);
    }
    return 0;
}