题意简述:

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

解法一(枚举放传送门位置,多次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的时间复杂度是,枚举所有传送门位置最坏情况是,计算当前传送门对答案的贡献是的,故总的时间复杂度为
空间复杂度:地图本身的二维数组,距离数组,标记数组,队列元素个数都是级别大小的,故总的空间复杂度为