题意：给你一张n*m的图，其中：
“ . ”代表可以走的空地
“ # ”代表不能走的墙
“ * ”代表传送门，当你从一个非传送们走到一个传送门的时候，你只能选择传送到除这个传送们外其他的传送门，如过没有其他传送们可以走，你就会死掉；当你到达传送门是由其他传送们传送到的，你既可以选择继续传送，也可以选择走到该传送们的相邻位置。
“ P ”代表初始位置
“ D ”代表目标位置
从出发位置开始，每次只能走到它相邻的位置，问你走到目标位置要走的最少步数，不能走到输出“ -1 ”.
思路：因为要找的是最少步数，所有我用的是bfs，对于所有的传送门，我们要分两种时间来处理，一种是到达该传送们的时间的最短时间，用vt数组保存，一种是当该传送们可以向四周走的时候的时间，用use数组保存，，我们先将他们初始化为0（代表未到或者不能往四周走），每次到达传送门的时候，如果它的vt时间非零，那我们用它来更新其他所有use为零的传送门（因为当从一个传送们到另一个传送门时，我们可以选择往四周走或者继续传送）（代表该传送门可以往四周走），否则它的use时间来更新（因为它没有其他的非传送门位置可以到达它，所以只能用use时间来更新其他use为零的点）（我们是用bfs，所以我们一定是按照时间的非递减来更新每一个点的，每个点）（每一个传送门只要能往四周走的时候我们就不用更新他的use值了，差不多第一次到达传送门时（假设有k个传送门），我们用到达它的vt时间来更新其他k-1个传送门的use时间，然后用第二个到达的传送门更新第一个传送门的use值就可以了，以后都不要再继续传送了，因为每个传送门都可以向四周走了，再传送时间肯定不是最短的
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
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<st> v;//存传送门的位置
queue<st> 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
",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<v.size();j++){//继续传送到其他没到过的传送门
if((v[j].x!=a.x)||(v[j].y!=a.y)){//不能传自己
if(!use[v[j].x][v[j].y]){//如果它没到过
if(!vt[a.x][a.y])//如果更新它的时候它还没有被非传送门的位置更新
use[v[j].x][v[j].y]=use[a.x][a.y]+1;
else
use[v[j].x][v[j].y]=tm+1;
lg=1;
q.push(v[j]);
}
}
}
}
if(use[a.x][a.y]){//向四周走
for(i=0;i<4;i++){
b.x=a.x+x1[i];
b.y=a.y+y1[i];
if(check(b)&&s[b.x][b.y]!='*'){//不能走传送门
vt[b.x][b.y]=use[a.x][a.y]+1;
q.push(b);
}
}
}
}
else{
for(i=0;i<4;i++){//如果该点是非传送门，正常先四周走
b.x=a.x+x1[i];
b.y=a.y+y1[i];
if(check(b)){
vt[b.x][b.y]=tm+1;//更新到达时间
q.push(b);
}
}
}
}
}
int main(){
int t;
int i,j;
int nb;
scanf("%d",&t);
nb=0;
while(t--){
nb++;
memset(vt,0,sizeof(vt));
memset(use,0,sizeof(use));//初始化
v.clear();
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
getchar();
for(j=1;j<=m;j++){
scanf("%c",&s[i][j]);
if(s[i][j]=='P'){
a1.x=i;
a1.y=j;
}
else if(s[i][j]=='D'){
b1.x=i;
b1.y=j;
}
else if(s[i][j]=='*'){//保存传送门位置
c.x=i;
c.y=j;
v.push_back(c);
}
}
}
bfs();
printf("Case %d: ",nb);
if(!vt[b1.x][b1.y]){
printf("impossible
");
}
else{
printf("%d
",vt[b1.x][b1.y]-1);
}
}
return 0;
}
）
代码：