题目描述

二维平面上有一个迷宫，在迷宫内部有起点和终点。现在要从起点走到终点，并且只能选择前后左右四个方向行走，而且显然不能走到篱笆上，也不能走出迷宫的边界。每次移动到相邻格子的耗时肯定是1。同时在挑战开始前，可以进行适当的路面调整，使得在南北方向（数据中的上下方向）的移动时间由1变成实数v。调整后，会给出一个实数L最快情况下，将花费L的时间由起点到达终点。求满足条件的v。

任务保证有解。

并且，迷宫中一定没有水平的从起点到终点的通路。

输入格式

输入文件包含多个测试点。第一行包含一个整数，表示测试点的数目。每个测试点的第一行包含实数v和两个整数N,M。

之后N行是迷宫的描述，每行包含M个字符。其中空格代表空地，S代表起点，E代表终点，#代表篱笆。

输出格式

对于每组测试数据，在单独的一行内输出v的值，保留5位小数。

对于100%的数据，满足N,M<=100，并且最后v的答案不会超过10

思路

二分答案v

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define pr pair<int,int>
using namespace std;
double L;	
int n,m;
bool a[101][101];
int qx,qy,dx,dy;
int xz[]={0,1,0,-1};
int yz[]={1,0,-1,0};
int can(double v)
{
	double f[101][101];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			f[i][j]=1e9;
		}
	}
	f[qx][qy]=0;
	queue<pr>q;
	q.push(make_pair(qx,qy));
	while(q.size())
	{
		int tx=q.front().first,ty=q.front().second;
		q.pop();
		bool flag=0;
		for(int i=0;i<4;i++)
		{
			int xx=tx+xz[i],yy=ty+yz[i];
			if(xx<=0||yy<=0||xx>n||yy>m||a[xx][yy]==1)
			{
				continue;
			}
			double c=f[tx][ty];
			if(i&1)
			{
				c+=v;
			}
			else
			{
				c+=1;
			}
			if(c<f[xx][yy])
			{
				//cout<<xx<<"----"<<yy<<endl;
				f[xx][yy]=c;
				if(xx==dx&&yy==dy)
				{
					flag=1;
					break;
				}
				q.push(make_pair(xx,yy));
			}
		}
		if(flag)
		{
			break;
		}
	}
	//cout<<"------"<<v<<"-----"<<f[dx][dy]<<"---"<<L<<endl;
	if(f[dx][dy]<L)
	{
		return -1;
	}
	if(f[dx][dy]>L)
	{
		
		return 1;
	}	
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof(a));
		cin>>L>>n>>m;
	    for(int i=1;i<=n;i++)
	    {
	    	string c;
	        getline(cin,c);
	        if(!c.size())
			{
				getline(cin,c);
			}
			int len=c.size();
	        for (int j=0;j<len;j++)
			{
				if(c[j]=='#')
				{
					a[i][j+1]=1;
				}
				else if(c[j]=='S')
				{
					qx=i;
					qy=j+1;
				}
				else if(c[j]=='E')
				{
					dx=i;
					dy=j+1;
				}				
			}
	    }
	    double l=0,r=10;
	    while(r-l>=1e-7)
	    {
			double mid=(l+r)/2;
			int c=can(mid);
			//cout<<"------"<<l<<' '<<r<<' '<<c<<endl;
			if(c==0)
			{
				l=mid;
				break;
			}
			else if(c==1)
			{
				r=mid;
			}
			else
			{
				l=mid;
			}
		}
		printf("%.5lf\n",l);
	}
	return 0;
}

只能过样例（WA），应该是有很大的错误