梦熊

2024--NOIP端午联赛0609--多校联测【补题】t1题面

#include<bits/stdc++.h>
using namespace std;
long long n,m,sx,sy,tx,ty,g[105][105],vis[105][105],h[105][105],l[105][105];
long long dx[]={0,1,0,-1,0};
long long dy[]={0,0,1,0,-1};
double s,ans=0x3f3f3f3f;
queue<pair<long long,long long> >q;
int main()
{
	freopen("msg.in","r",stdin);
	freopen("msg.out","w",stdout);
	cin>>n>>m>>sx>>sy>>tx>>ty ;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];
	cin>>s;
	vis[sx][sy]=1;
	q.push(make_pair(sx,sy));
	while(q.size())
	{
		long long x=q.front().first,y=q.front().second;
		if(x==tx&&y==ty)
		{
			if(h[tx][ty]==0)
			{
				cout<<"0.000";
				return 0;
			}
			ans=min(ans,(s-l[tx][ty])/h[tx][ty]);
		}
		q.pop();
		for(int i=1;i<=4;i++)
		{
			long long xx=x+dx[i],yyy=y+dy[i];
			if((!vis[xx][yyy])&&(!g[xx][yyy])&&(xx<=n)&&(1<=xx)&&(yyy<=m)&&(1<=yyy))
			{
				vis[xx][yyy]=1;
				h[xx][yyy]=h[x][y];
				l[xx][yyy]=l[x][y];
				q.push(make_pair(xx,yyy));
				if(xx!=x)h[xx][yyy]++;
				else l[xx][yyy]++;
			}
		}
	}
	printf("%.3lf\n",ans);
}

40 wa了