反向搜索，以终点为起点，广度优先搜索

解题思路:反向搜索，以终点为起点，广度优先搜索

用mp<pair,vector<pari>>来存储某个点存放的门
注意事项:

在搜索四个方向后，再加上这个点拥有的门，其他的与广搜无异

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=2e3+10;

typedef pair<int,int> pll;

bool v[N][N];

long long int n,m,x3,y3,x2,y2,ans;

map<pll,vector<pll>> s;

queue<pll> q;

long long int dis[N][N];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int main()

{

    cin>>n>>m;

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

    {

        cin>>x3>>y3>>x2>>y2;

        s[{x3,y3}].push_back({x2,y2});

        s[{x2,y2}].push_back({x3,y3});

    }

    q.push({n,n});

    v[n][n]=true;

    dis[n][n]=0;

    while(q.empty()==0)

    {

        pll t=q.front();

        q.pop();

        int x=t.first,y=t.second;

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

        {

            int tx=x+dir[k][0],ty=y+dir[k][1];

            if(v[tx][ty]==false&&tx>=1&&tx<=n&&ty>=1&&ty<=n)

            {

                //printf("%d %d to %d %d\n",x,y,tx,ty);

                dis[tx][ty]=dis[x][y]+1;

                v[tx][ty]=1;

                q.push({tx,ty});

            }

            if(s.find({x,y})!=s.end())

                {

                    for(int j=0;j<s[{x,y}].size();j++)

                        {

                            tx=s[{x,y}][j].first,ty=s[{x,y}][j].second;

                            if(v[tx][ty]==false&&tx>=1&&tx<=n&&ty>=1&&ty<=n)

                            {

                                dis[tx][ty]=dis[x][y]+1;

                                v[tx][ty]=1;

                                q.push({tx,ty});

                            }

                        }

                }

        }

    }

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

        for(int j=1;j<=n;j++) ans+=dis[i][j];

    double up=ans,down=n*n;

    printf("%.2f\n",up/down);

    return 0;

}