CDOJ(UESTC) 149 解救小Q（bfs中涉及传送带的问题）

╰+攻爆jí腚メ 2024-02-17 20:25 19阅读 0赞

## 解救小Q ##

###### Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) ######

小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到传送阵的另一头。

现在请你帮助love8909算一算，他至少需要走多少步才能解救到小Q？

### Input ###

第一行为一个整数*T*

，表示测试数据组数。

每组测试数据第一行为两个整数*N*

，  *M*，(  1≤*N*,*M*≤50

)表示迷宫的长和宽。

接下来有*N*

行，每行  *M*

个字符，是迷宫的具体描述。

*  `.`表示安全的位置
 *  `#`表示陷阱，
 *  `Q`表示小Q的位置
 *  `L`表示love8909所在位置，

数据保证love8909只有一个，数据也保证小Q只有一个。

小写字母`a`\-`z`表示分别表示不同的传送阵，数据保证传送阵两两配对。

### Output ###

每组数据输出一行，解救小Q所需的最少步数，如果无论如何都无法救小Q，输出`-1`。

### Sample input and output ###

<table> 
 <thead> 
  <tr> 
   <th style="width:50%">Sample Input</th> 
   <th style="width:50%">Sample Output</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td> <pre>2

5 5
....L
.###.
b#b#a
##.##
...Qa

5 5
....L
.###.
.#.#.
##.##
...Q.</pre> </td> 
   <td> <pre>3
-1</pre> </td> 
  </tr> 
 </tbody> 
</table>

分析：个人感觉传送带问题还得多留意一下， 每次遇到bfs中的传送带问题，都因为考虑不全贡献几次WR；言归正传，首先肯定是bfs求解，四个方向（上下左右），这点题目中给的并不怎么明显。下面就该关心传送带的处理了，因为题目保证传送带是**两两配对**的，所以每种传送带要么出现两次，要么不出现；这里我用vec<node>vec\[28\]来储存每一对，只要知道一个传送带的坐标，非常方便的就可以求出另外一个的坐标，下面就要特别小心了：同一对传送带的**d值相同**，从传送带的这端（1端）出发到另一端（2端），我们需要标记**出发端**的已经访问，（另一端不行，因为我们还可以从另一端过来）然后将2端加入队列判断……

做题过程中纠结了这样一个问题，就是当传输到另一端的时候，我不出去，d值加1，然后从这端出发（也就是说方向变成了五个，包括(0,0)），分析题意好像并不能这样啊，需要出去然后在回来，才能被传送到另一端…………（改了之后就A了）

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn=50+5;
    char g[maxn][maxn];
    int d[maxn][maxn];
    int vis[maxn][maxn]; //用于传送带的节点访问标识 
    int n,m;
    
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    }Q,L;
    vector<node>vec[28];  //储存传送带的两两配对关系 
    int dir[][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    bool isValid(node &nd){
    	return nd.x>=0&&nd.x<n && nd.y>=0&&nd.y<m;
    }
    void bfs(){
    	memset(d,-1,sizeof(d));
    	memset(vis,0,sizeof(vis));
    	queue<node>q;
    	q.push(L);
    	d[L.x][L.y]=0;
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		
    		if(u.x==Q.x && u.y==Q.y){
    			printf("%d\n",d[u.x][u.y]);
    			return ;
    		}
    		
    		for(int i=0;i<4;i++){
    			int x1=dir[i][0]+u.x, y1=dir[i][1]+u.y;
    			node v=node(x1,y1);
    			if(isValid(v) && g[v.x][v.y]>='a'&&g[v.x][v.y]<='z' && !vis[v.x][v.y]){
    				d[v.x][v.y]=d[u.x][u.y]+1;    
    				vis[v.x][v.y]=1;  //传送带开始的这一头d值+1后，做已经访问标识。
    				char ch=g[v.x][v.y]; 
    				int x=vec[ch-'a'][0].x;
    				int y=vec[ch-'a'][0].y;
    				if(v.x==x&&v.y==y){ //每个vec[i]中有两个传送带节点坐标，知道其中一个就可以求另一个。 
    					v.x=vec[ch-'a'][1].x;
    					v.y=vec[ch-'a'][1].y;
    				}
    				else {
                        v.x=vec[ch-'a'][0].x;
    					v.y=vec[ch-'a'][0].y;					
    				}
    				
    					d[v.x][v.y]=d[x1][y1]; //同一对传送带保持d值相同 
    					q.push(v);
    			}
    			
    			else {
    				if(isValid(v) && d[v.x][v.y]==-1 && g[v.x][v.y]!='#'){
    					q.push(v);
    					d[v.x][v.y]=d[u.x][u.y]+1;
    				}
    			}
    		}
    	}
    	printf("-1\n");
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		getchar(); //吃掉换行 
    		for(int i=0;i<n;i++){
    			for(int j=0;j<m;j++){
    				scanf("%c",&g[i][j]);
    				if(g[i][j]=='Q')Q.x=i,Q.y=j;
    				else if(g[i][j]=='L')L.x=i,L.y=j;
    				else if(g[i][j]>='a'&&g[i][j]<='z')
    				vec[g[i][j]-'a'].push_back(node(i,j));
    			}
    			getchar();
    		}
    		
    		bfs();
    		
    		for(int i=0;i<26;i++)vec[i].clear(); //记得要清空容器 ！ ！！ 
    	}
    	return 0;
    }

另外呢再附上两组测试数据！

5 5  
....L  
.\#a\#.  
b\#Q\#.  
\#\#b\#\#  
..a..

输出 6 （这组的路径：(0,4)->(0,3)->(0,2)->(1,2),传输带,(4,2)->(4,3)or(4,1)->(4,2)->(1,2)->(2,2)）d值得计算刚才已经说过了。（也许会疑问传送带出发端不是已经被标记访问过了吗，为什么到回去呢？实际上此时的第一次的出发端已经被当成第二次的到达端，直接被加入队列，执行下一次出队列的四个方向的判断）

5 5  
....L  
.\#\#\#.  
a\#Q\#.  
\#\#.\#\#  
a.b.b

输出 12