2022迷宫--反向bfs-最短路效应+传送门

bfs先到的点一定是最短的，因为他是向外扩散，每一层每一层的扩散，和dfs本质区别

终点b（vis兼路径长）设为1 

#include<bits/stdc++.h>
#define inf 5e5+11
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
int n,m;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int b[2011][2011];
vector<pair<int,int> > a[2011][2011];
ll s;
int c;
queue<pair<int,int> > q;
void bfs()///bfs最短路效应 
{
	while(q.size())
	{
		int x=q.front().first;
		int y=q.front().second;
		s+=b[x][y]-1;///终点b（vis兼路径长）设为1 
		q.pop();
		for(int i=0;i<4;i++)
		{
			int wx=x+dx[i];
			int wy=y+dy[i];
			if(wx>=1&&wx<=n&&wy>=1&&wy<=n&&!b[wx][wy])///wxwy原来没有被走过，现在就是最短 
			{
				b[wx][wy]=b[x][y]+1;
				q.push({wx,wy});
			}
		}
		for(int i=0;i<a[x][y].size();i++)///走传送门 
		{
			pair<int,int> t=a[x][y][i];
			int tx=t.first;
			int ty=t.second;
			if(b[tx][ty]) continue;///原来走过就不用传了，因为最短路 
			b[tx][ty]=b[x][y]+1;
			q.push({tx,ty});
		}
		
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int dx,dy,tx,ty;
		cin>>dx>>dy>>tx>>ty;
		a[dx][dy].push_back({tx,ty});///储传送门 
		a[tx][ty].push_back({dx,dy});
	}
	b[n][n]=1;
	q.push({n,n});
	bfs();
	printf("%.02lf",(double)s/1.0/n/n);
    return 0;
}