Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

int sx,sy,tx,ty;

double s;

#define MAXN 110

int p[MAXN][MAXN];

const double eps = 1e-7;

double d[MAXN][MAXN];

#define INF 1000000000000

struct pos{int x,y;};

bool v[MAXN][MAXN];

int mx[4] = {0,0,1,-1},my[4] = {1,-1,0,0};

double query(double l)

{

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

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

			d[i][j] = INF;

	d[sx][sy] = 0;

	memset(v,false,sizeof(v));

	queue<pos> q;q.push((pos){sx,sy});

	while(!q.empty())

	{

		pos k = q.front();q.pop();

		v[k.x][k.y] = false;

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

		{

			if(k.x + mx[i] >= 1 && k.x + mx[i] <= n && k.y + my[i] >= 1 && k.y + my[i] <= m && p[k.x + mx[i]][k.y + my[i]] == 0)

			{

				if(d[k.x + mx[i]][k.y + my[i]] > d[k.x][k.y] + (i < 2 ? 1.0 : l))

				{

					d[k.x + mx[i]][k.y + my[i]] = d[k.x][k.y] + (i < 2 ? 1.0 : l);

					if(!v[k.x + mx[i]][k.y + my[i]])

					{

						v[k.x + mx[i]][k.y + my[i]] = true;

						q.push((pos){k.x + mx[i],k.y + my[i]});

					}

				}

			}

		}

	}

	return d[tx][ty];

}

int main()

{

	freopen("maze.in","r",stdin);

	freopen("maze.out","w",stdout);

	scanf("%d%d",&n,&m);

	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);

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

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

			scanf("%d",&p[i][j]);

	scanf("%lf",&s);

	double l = 0,r = s,mid;

	while(r - l > eps)

	{

		mid = (l + r) / 2;

		if(query(mid) > s)r = mid;

		else l = mid;

	}

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

	fclose(stdin);

	fclose(stdout);

	return 0;

}