HDU 1728 逃离迷宫（BFS+转弯次数+转弯方向）

水深无声 2024-02-18 16:36 51阅读 0赞

<table style="font-family:&quot;Times New Roman&quot;; word-wrap:break-word"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="word-wrap:break-word; width:980px; margin-top:10px">  
     <div style=""> 
      <span style="margin-right:20px"><a href="http://acm.hdu.edu.cn/contests/contest_list.php" style="color:red" rel="nofollow">新生赛（点击红色的Registerring）</a><br> </span> 
     </div>  
    </div> </td> 
  </tr> 
  <tr> 
   <td align="center"> <h2 style="color:rgb(26,92,200)">逃离迷宫</h2> <strong><span style="font-family:Arial; color:green">Time Limit: 1000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 32768/32768 K (Java/Others)<br> Total Submission(s): 29797&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 7313<br> </span></strong><br> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Problem Description 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      　　给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？ 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      　　第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中， 
     <br> 　　第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x 
     <sub>1</sub>, y 
     <sub>1</sub>, x 
     <sub>2</sub>, y 
     <sub>2</sub>&nbsp;(1 ≤ k ≤ 10, 1 ≤ x 
     <sub>1</sub>, x 
     <sub>2</sub>&nbsp;≤ n, 1 ≤ y 
     <sub>1</sub>, y 
     <sub>2</sub>&nbsp;≤ m),其中k表示gloria最多能转的弯数，(x 
     <sub>1</sub>, y 
     <sub>1</sub>), (x 
     <sub>2</sub>, y 
     <sub>2</sub>)表示两个位置，其中x 
     <sub>1</sub>，x 
     <sub>2</sub>对应列，y 
     <sub>1</sub>, y 
     <sub>2</sub>对应行。 
     <br> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left">
      　　每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Input 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
      
       
      <div style="font-family:&quot;Courier New&quot;,Courier,monospace">
       
        
       
       2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
      
      
       
      </div></pre> 
    </div> 
    <div style="height:auto; margin:0px">
      &nbsp; 
    </div> <br> 
    <div style="height:38px; padding:0px 14px; color:rgb(124,169,237); font-size:18px; font-family:Arial; font-weight:bold">
      Sample Output 
    </div> 
    <div style="height:auto; margin:0px; padding:0px 20px; font-size:14px; font-family:&quot;Times New Roman&quot;; text-align:left"> 
     <pre style="word-wrap:break-word; white-space:pre-wrap; margin-top:0px; margin-bottom:0px">      
      
       
      <div style="font-family:&quot;Courier New&quot;,Courier,monospace">
       
        
       
       no
yes
      
      
       
      </div></pre> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

思路：此题有两个比较坑的地方：1、数据的输入时，注意审题 ； 2、转弯次数和转弯方向，这里我通过用四维数组来处理d\[i\]\[j\]\[c\]\[cnt\] 用以标志在坐标为(i，j) 、方向为c、转弯次数cnt 的点是否被访问过了 。 问：是否会出现无限循环？ 不会，当转弯次数大于k是不会再加入队列。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    using namespace std;
    const int maxn = 100+2;
    char g[maxn][maxn];
    int d[maxn][maxn][30][12]; 
    struct node{
    	int x,y;
    	char c ; //当前方向，有四种值 z y s x 即左 右 上 下 
    	int cnt; //记录转弯次数 
    	node(int x,int y,int c, int cnt):x(x),y(y),c(c),cnt(cnt){}
    	node(){}
    } start,end1;
    
    int dx[4] = {0,0,-1,1}; //左、右、上、下 
    int dy[4] = {-1,1,0,0};
    int k ; //转弯次数限制
    int n, m;
     
    void bfs(){
    	queue<node> q;
    	memset(d,0,sizeof(d));
    	q.push(start);
    	d[start.x][start.y][0][0] = 1;
    	while(!q.empty()){
    		node u = q.front(); q.pop();
    		if(u.x == end1.x && u.y == end1.y) {
    			
    			printf("yes\n");
    			return ;
    		}
    		
    		for(int i = 0; i < 4; i++){
    			int t = 0;
    			if(u.c == 'z' && i != 0) t = 1; //向左 
    			if(u.c == 'y' && i != 1) t = 1; //向右
    			if(u.c == 's' && i != 2) t = 1; //向上 
    			if(u.c == 'x' && i != 3) t = 1; //向下 
    			if(u.cnt + t > k) continue;
    			
    			char c ;
    			switch(i){
    				case 0: c = 'z'; break;
    				case 1: c = 'y';break;
    				case 2: c = 's';break;
    				case 3: c = 'x';
    			}
    			node v = node(u.x + dx[i],u.y + dy[i],c,u.cnt+t);
    			if(v.x < 1 || v.x > n || v.y < 1 || v.y > m) continue;
    			if(d[v.x][v.y][v.c-'a'][v.cnt] || g[v.x][v.y] == '*') continue;
    			q.push(v);
    			d[v.x][v.y][v.c-'a'][v.cnt] = 1; 
    		}
    	}
    	printf("no\n");
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		for(int i = 1; i <= n; i++)
    		scanf("%s",g[i]+1);
    		
    		scanf("%d%d%d%d%d",&k,&start.y,&start.x,&end1.y,&end1.x);
    		start.c = '0' ;
    		start.cnt = 0;
    		bfs();
    	}
    	return 0;
    }