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+剪枝
转弯数

三、代码

 //dfs+剪枝

 //根据下一点如果遍历过而且转弯数小于当前点到达下一点的转弯数（其他情况类似）进行剪枝

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int maxn = 1e4+;

 #define INF 0x3f3f3f3f

 char a[][];

 int n,m,k,T,x1,y1,x2,y2;                    //起点坐标(is,js)，门的坐标(id,jd)

 int to[][]={,,-,,,,,-};

 int vis[][];                        //记录到达某点所需的转弯数

 bool flag;

 void dfs(int x,int y,int dir)            //cnt为当前转弯的次数

 {

     int mx,my;

     if(x==x2 && y==y2){

         if(vis[x][y]<=k)

             flag = ;

         return;

     }

     if(vis[x][y]>k)    return;                //大于k时已晕，不行

     //如果(x,y)和终点(x2,y2),既不在同一行也不在同一列，那么要想到终点至少需要转一次，但现在已经转够k次了，故不行

     if(vis[x][y]==k && x!=x2 && y!=y2)    return;

     for(int i=;i<;i++){

         mx = x + to[i][];

         my = y + to[i][];

         if(mx< || mx>m || my< || my>n)    continue;

         if(vis[x][y]>vis[mx][my] || a[mx][my]=='*')        continue;         //这里相等的情况不能剪掉

         //这条if和上面的差不多，目的是：如果从(x,y)走一步到(tx,ty)需要转一次话，并且转过之后vis[x][y]+1依然比vis[tx][ty]大的话，也不符合

         if(dir!=- && i!=dir && vis[mx][my]<vis[x][y]+)    continue;

         vis[mx][my] = vis[x][y];

         if(dir!=- && i!=dir){

             vis[mx][my]++;

         }

         dfs(mx,my,i);

         if(flag==)

             return;

     }

 } 

 int main()

 {

     cin>>T;

     while(T--){

         scanf("%d%d",&m,&n);

         for(int i=;i<=m;i++){

             getchar();

             for(int j=;j<=n;j++){

                 scanf("%c",&a[i][j]);

             }

         }

         getchar();

         cin>>k>>y1>>x1>>y2>>x2;                //注意，这里是先接y，再接x

         memset(vis,INF,sizeof(vis));        //因为在dfs()中剪枝要去最小的转弯次数，所以vis要初始化成最大

         vis[x1][y1] = ;                    //转0次弯

         flag = ;

         dfs(x1,y1,-);

         if(flag==)    printf("yes\n");

         if(flag==)    printf("no\n");

     }

     return ;

 }

巴特西

DFS（5）——hdu1728逃离迷宫

最新文章

热门文章