题意简述：

给你一个大小的网格迷宫，迷宫的每个格子分为四种类型：空地、障碍物、唯一固定传送门、可放置传送门位置
游戏刚开始时，你可以选择一个『可放置传送门位置』放置一个传送门，这个传送门可以和『唯一固定传送门』互通
刚开始玩家处于迷宫第行第列，玩家每次可以走上、下、左、右四个方向，且不能走到障碍物，不能超界，遇到传送门可以选择传送也可以选择不传送
问玩家最少花多少步可以到达迷宫第行第列？

解法一（枚举放传送门位置，多次BFS，不可AC）

我们可以枚举所有『可放置传送门位置』放置传送门，并且在当前条件下利用BFS求出起点到终点的最少步数。
代码： 
class Solution {
public:
    const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向数组
    struct node{
        int x,y;//存储位置的结构体
        inline node(int x,int y):x(x),y(y){}
    };
    bool vis[501][501];//vis[x][y] 标记该点是否访问过
    int dis[501][501];//dis[x][y]表示起点到点(x,y)的最少步数
    void bfs(int x,int y,int dx,int dy,int N,vector<vector<int> >& a){
        memset(vis,0,sizeof vis);//初始化全部没访问
        memset(dis,0x3f,sizeof dis);//初始化最少步数一个极大值
        queue<node> que;//队列
        vis[0][0]=true;//标记起点访问
        dis[0][0]=0;//起点到起点步数为0
        que.push(node(0,0));//推入队列
        while(!que.empty()){
            node t=que.front();//弹出队头
            que.pop();
            int ux=t.x,uy=t.y;
            for(int i=0;i<4;i++){//四个方向
                int vx=ux+dir[i][0],vy=uy+dir[i][1];
                if(vx<0||vx>=N||vy<0||vy>=N||vis[vx][vy]||a[vx][vy]==1)continue;
                vis[vx][vy]=true;
                dis[vx][vy]=dis[ux][uy]+1;
                que.push(node(vx,vy));
            }
            if(a[ux][uy]==3&&!vis[x][y]){//如果当前位置是 唯一固定传送门，那么可选择往传送门位置扩展
                vis[x][y]=true;
                dis[x][y]=dis[ux][uy]+1;
                que.push(node(x,y));
            }
            if(ux==x&&uy==y&&!vis[dx][dy]){//如果当前位置是放置传送门的位置，那么可选择往 唯一固定传送门扩展
                vis[dx][dy]=true;
                dis[dx][dy]=dis[ux][uy]+1;
                que.push(node(dx,dy));
            }
        }
    }
    int solve(int N, vector<vector<int> >& a) {
        int dx=0,dy=0;//唯一固定传送门位置
        vector<node> pos_datas;//所有可放置传送门的位置
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(a[i][j]==2){//可放置
                    pos_datas.push_back(node(i,j));
                }else if(a[i][j]==3){//唯一固定
                    dx=i,dy=j;
                }
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0;i<pos_datas.size();i++){
            //枚举传送门放哪
            int x=pos_datas[i].x,y=pos_datas[i].y;
            bfs(x,y,dx,dy,N,a);
            ans=min(ans,dis[N-1][N-1]);//答案取最小
        }
        return ans;
    }
};
时间复杂度：，最坏情况下，可放置传送门的位置数量是级别的，每次BFS由于每个点只会访问一次，故单次BFS时间复杂度是，故总的时间复杂度是
空间复杂度：，地图本身的二维数组，距离数组，标记数组，队列元素个数都是级别大小的，故总的空间复杂度为

解法二（双起点BFS，中间插点（传送门）求解）

我们可以用表示起点到点不加传送门的最少步数
用表示终点到点不加传送门的最少步数
显然上面两个数组可以用两次BFS求得
我们记为『唯一固定传送门』位置
记为传送门位置
考虑枚举每一个『可放置传送门』的位置，若起点到终点的路线经过该点，分为两种情况：
    1. 起点 ->『唯一固定传送门』-> 传送门 -> 终点
    
    对应答案为：
    2. 起点 -> 传送门 -> 『唯一固定传送门』 -> 终点
    
    对应答案为：
综上所述，枚举当前点放传送门对答案的贡献为
我们可以枚举所有传送门的位置，然后取贡献的最小值即可
代码： 
class Solution {
public:
    const int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//方向数组
    struct node{
        int x,y;//位置结构体
        inline node(int x,int y):x(x),y(y){}
    };
    int dis[2][501][501];//距离数组
    bool vis[501][501];//标记访问数组
    void bfs(int sx,int sy,int k,int N,vector<vector<int> >& a){
        memset(vis,0,sizeof vis);
        queue<node> que;
        que.push(node(sx,sy));
        vis[sx][sy]=true;
        dis[k][sx][sy]=0;
        while(!que.empty()){
            node t=que.front();
            que.pop();
            int ux=t.x,uy=t.y;
            for(int i=0;i<4;i++){
                //四个方向扩展
                int vx=ux+dir[i][0],vy=uy+dir[i][1];
                if(vx<0||vx>=N||vy<0||vy>=N||vis[vx][vy]||a[vx][vy]==1)continue;
                dis[k][vx][vy]=dis[k][ux][uy]+1;
                vis[vx][vy]=true;
                que.push(node(vx,vy));
            }
        }
    }
    int solve(int N, vector<vector<int> >& a) {
        memset(dis,0x3f,sizeof dis);
        bfs(0,0,0,N,a);//左上角为起点
        bfs(N-1,N-1,1,N,a);//右下角为起点
        int ans=dis[0][N-1][N-1];//首先不用传送门的答案
        int dx=0,dy=0;//唯一固定传送门位置
        vector<node> pos_datas;//可放置传送门位置
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(a[i][j]==3){
                    dx=i,dy=j;
                }else if(a[i][j]==2){
                    pos_datas.push_back(node(i,j));
                }
            }
        }
        for(int i=0;i<pos_datas.size();i++){
            int x=pos_datas[i].x,y=pos_datas[i].y;
            //枚举所有传送门
            ans=min(ans,dis[0][x][y]+1+dis[1][dx][dy]);
            ans=min(ans,dis[0][dx][dy]+1+dis[1][x][y]);
        }
        return ans;
    }
};
时间复杂度：，两次BFS的时间复杂度是，枚举所有传送门位置最坏情况是，计算当前传送门对答案的贡献是的，故总的时间复杂度为
空间复杂度：，地图本身的二维数组，距离数组，标记数组，队列元素个数都是级别大小的，故总的空间复杂度为