题意：给你一张n*m的图，其中：

“ . ”代表可以走的空地

“ # ”代表不能走的墙

“ * ”代表传送门，当你从一个非传送们走到一个传送门的时候，你只能选择传送到除这个传送们外其他的传送门，如过没有其他传送们可以走，你就会死掉；当你到达传送门是由其他传送们传送到的，你既可以选择继续传送，也可以选择走到该传送们的相邻位置。

“ P ”代表初始位置

“ D ”代表目标位置

从出发位置开始，每次只能走到它相邻的位置，问你走到目标位置要走的最少步数，不能走到输出“ -1 ”.

思路：因为要找的是最少步数，所有我用的是bfs，对于所有的传送门，我们要分两种时间来处理，一种是到达该传送们的时间的最短时间，用vt数组保存，一种是当该传送们可以向四周走的时候的时间，用use数组保存，，我们先将他们初始化为0（代表未到或者不能往四周走），每次到达传送门的时候，如果它的vt时间非零，那我们用它来更新其他所有use为零的传送门（因为当从一个传送们到另一个传送门时，我们可以选择往四周走或者继续传送）（代表该传送门可以往四周走），否则它的use时间来更新（因为它没有其他的非传送门位置可以到达它，所以只能用use时间来更新其他use为零的点）（我们是用bfs，所以我们一定是按照时间的非递减来更新每一个点的，每个点）（每一个传送门只要能往四周走的时候我们就不用更新他的use值了，差不多第一次到达传送门时（假设有k个传送门），我们用到达它的vt时间来更新其他k-1个传送门的use时间，然后用第二个到达的传送门更新第一个传送门的use值就可以了，以后都不要再继续传送了，因为每个传送门都可以向四周走了，再传送时间肯定不是最短的

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct st{	int x,y;};char s[210][210];//存地图 int vt[210][210];//到达时间 int x1[4]={0,1,0,-1};int y1[4]={1,0,-1,0};int use[210][210]; //存每个传送门可以向四周走的时间 vector
         
           v;//存传送门的位置 queue
          
            q; st a1,b1,c;int n,m,lg;bool check(st a){//检验是否能走 if(a.x>0&&a.x<=n&&a.y<=m&&a.y>0&&s[a.x][a.y]!='#'&&!vt[a.x][a.y]) return true; return false;}int bfs(){ int i,j; while(!q.empty()) q.pop(); q.push(a1); vt[a1.x][a1.y]=1;//标记初始位置 st a,b;\ lg=1; while(!q.empty()){ a=q.front(); q.pop(); int tm=vt[a.x][a.y];//该点的到达时间 // printf("%d %d %d %d\n",a.x,a.y,tm,use[a.x][a.y]); if(s[a.x][a.y]=='*'){//当是传送门的时候 if(lg&&v.size()>1){//如果有不止一个传送门并且还有传送门不能向四周走 c.x=a.x; c.y=a.y; lg=0; for(j=0;j
          
         
        
       
      
     

 

　　

）

代码：