题目大意:网格图,给出时间L,v为通过一个格子的时间,求最大的v
题解:题目里提示了一定会走竖直道路,同时v很小,当然是大力二分了。检验一下能否在L的时间内到达。
我懒得写了,抄下黄学长的……
我的收获:……
#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;
}