DFS（5）——hdu1728逃离迷宫

一、题目回顾

Problem Description

　　给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？

Input

　　第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
　　第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x₁, y₁, x₂, y₂ (1 ≤ k ≤ 10, 1 ≤ x₁, x₂ ≤ n, 1 ≤ y₁, y₂ ≤ m),其中k表示gloria最多能转的弯数，(x₁, y₁), (x₂, y₂)表示两个位置，其中x₁，x₂对应列，y₁, y₂对应行。

Output

　　每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

Sample Input

5 5

...**

*.**.

.....

*....

1 1 1 1 3

5 5

...**

*.**.

.....

*....

2 1 1 1 3

Sample Output

yes

题意：小明在点1（x₁ , y₁），请问他能在转弯次数不大于k的情况下到达点2（x₂ , y₂）吗？

二、解题思路

据说是经典BFS
DFS+剪枝
转弯数

三、代码

 1 //dfs+剪枝 
 2 //根据下一点如果遍历过而且转弯数小于当前点到达下一点的转弯数（其他情况类似）进行剪枝
 3 #include <iostream>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <cstring>
 7 using namespace std;
 8 const int maxn = 1e4+10;
 9 #define INF 0x3f3f3f3f
10 char a[105][105];
11 int n,m,k,T,x1,y1,x2,y2;                    //起点坐标(is,js)，门的坐标(id,jd) 
12 int to[4][2]={1,0,-1,0,0,1,0,-1};
13 int vis[105][105];                        //记录到达某点所需的转弯数
14 bool flag;
15 
16 void dfs(int x,int y,int dir)            //cnt为当前转弯的次数 
17 {
18     int mx,my;
19     if(x==x2 && y==y2){
20         if(vis[x][y]<=k)
21             flag = 1;
22         return;
23     }
24     if(vis[x][y]>k)    return;                //大于k时已晕，不行 
25     //如果(x,y)和终点(x2,y2),既不在同一行也不在同一列，那么要想到终点至少需要转一次，但现在已经转够k次了，故不行
26     if(vis[x][y]==k && x!=x2 && y!=y2)    return;         
27     for(int i=0;i<4;i++){
28         mx = x + to[i][0];
29         my = y + to[i][1];
30         if(mx<1 || mx>m || my<1 || my>n)    continue;
31         if(vis[x][y]>vis[mx][my] || a[mx][my]=='*')        continue;         //这里相等的情况不能剪掉
32         //这条if和上面的差不多，目的是：如果从(x,y)走一步到(tx,ty)需要转一次话，并且转过之后vis[x][y]+1依然比vis[tx][ty]大的话，也不符合
33         if(dir!=-1 && i!=dir && vis[mx][my]<vis[x][y]+1)    continue;    
34         vis[mx][my] = vis[x][y];
35         if(dir!=-1 && i!=dir){
36             vis[mx][my]++;
37         } 
38         dfs(mx,my,i);
39         if(flag==1)
40             return;
41     }
42 } 
43 
44 int main()
45 {
46     cin>>T;
47     while(T--){
48         scanf("%d%d",&m,&n);
49         for(int i=1;i<=m;i++){
50             getchar();
51             for(int j=1;j<=n;j++){
52                 scanf("%c",&a[i][j]);
53             }
54         }
55         getchar();    
56         cin>>k>>y1>>x1>>y2>>x2;                //注意，这里是先接y，再接x
57         memset(vis,INF,sizeof(vis));        //因为在dfs()中剪枝要去最小的转弯次数，所以vis要初始化成最大
58         vis[x1][y1] = 0;                    //转0次弯 
59         flag = 0;
60         dfs(x1,y1,-1);
61         if(flag==1)    printf("yes
");
62         if(flag==0)    printf("no
");
63     }
64     return 0;
65 }