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

题目链接 .

题目：

分析：

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

先输入一个m*n的数组

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

以起点为中心画十字

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

结合具体情况剪枝

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

<=k，是YES
else，是NO

图解例子：

第一次：

第二次：

把每个点当作起点向四个方向扩散

第三步：

第四步：

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");
		}
	}
}