HDU 1728 逃离迷宫（暴力遍历）：）

淩亂°似流年 2023-07-06 11:51 48阅读 0赞

## 题目链接 [HDU 1728 逃离迷宫 （暴力遍历）][HDU 1728 _]. ##

### 题目： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200218163922122.png]

### 分析： ###

要求在迷宫内两点间通路的最小拐弯数目

先输入一个m\*n的数组

再定义一个turn数组，表示起点到当前位置所需的最小拐弯数

以起点为中心画十字

##### 在十字上的拐弯数等于当前拐弯数 #####

结合具体情况剪枝

比较目标位置数值是否大于k

<=k，是YES  
else，是NO

### 图解例子： ###

#### 第一次： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]

#### 第二次： ####

把每个点当作起点向四个方向扩散  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]

#### 第三步： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

#### 第四步： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]

### AC代码： ###

package Three;
    
    import java.util.*;
    
    public class T1728 { 
    	public static char c[][];
    	public static int turn[][];
    	public static int m,n,k;
    	public static void full(int x,int y,int step){ 
    		if(step>k)return;
    		ArrayList<Integer> row=new ArrayList<Integer>();
    		ArrayList<Integer> col=new ArrayList<Integer>();
    		for(int i=x+1;i<n;i++){ 
    			if(c[y][i]=='*'||turn[y][i]<step)break;
    			if(c[y][i]=='.'&&turn[y][i]>step){ 
    				turn[y][i]=step;
    				row.add(i);
    			}
    		}
    		for(int i=x-1;i>=0;i--){ 
    			if(c[y][i]=='*'||turn[y][i]<step)break;
    			if(c[y][i]=='.'&&turn[y][i]>step){ 
    				turn[y][i]=step;
    				row.add(i);
    			}
    		}
    		for(int i=y+1;i<m;i++){ 
    			if(c[i][x]=='*'||turn[i][x]<step)break;
    			if(c[i][x]=='.'&&turn[i][x]>step){ 
    				turn[i][x]=step;
    				col.add(i);
    			}
    		}
    		for(int i=y-1;i>=0;i--){ 
    			if(c[i][x]=='*'||turn[i][x]<step)break;
    			if(c[i][x]=='.'&&turn[i][x]>step){ 
    				turn[i][x]=step;
    				col.add(i);
    			}
    		}
    		for(int t:row){ 
    			full(t,y,step+1);
    		}
    		for(int t:col){ 
    			full(x,t,step+1);
    		}
    	}
    	
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int t=sc.nextInt();
    		while(t-->0){ 
    			m=sc.nextInt();
    			n=sc.nextInt();
    			c=new char[m][n];
    			turn=new int[m][n];
    			for(int i=0;i<m;i++){ 
    				for(int j=0;j<n;j++){ 
    					turn[i][j]=Integer.MAX_VALUE;
    				}
    			}
    			for(int i=0;i<m;i++){ 
    				c[i]=sc.next().toCharArray();
    			}
    			k=sc.nextInt();
    			int x1=sc.nextInt();
    			int y1=sc.nextInt();
    			int x2=sc.nextInt();
    			int y2=sc.nextInt();
    			
    			turn[y1-1][x1-1]=0;
    			full(x1-1,y1-1,0);
    			
    			System.out.println(turn[y2-1][x2-1]<=k?"yes":"no");
    		}
    	}
    }

[HDU 1728 _]: http://acm.hdu.edu.cn/showproblem.php?pid=1728
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200218163902312.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[20200218163922122.png]: https://img-blog.csdnimg.cn/20200218163922122.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200218165546129.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200218165807813.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200218170027764.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020021817015911.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70